HDU 4960(또 다른 OCD 환자 구간 dp)

Another OCD Patient Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1320 Accepted Submission(s): 459
Problem Description 은 하나의 수열 을 알 고 있 습 니 다.이 제 는 k 세그먼트 로 나 누 어 각 세그먼트 와 구 성 된 새로운 수열 의 답문 을 요구 하고 합병 대가 가 가장 적 습 니 다.합병의 대 가 는∑ki=1a[len](len 은 이 단락 의 길이)
Input The input contains multiple test cases.
The first line of each case is an integer N (0 < N <= 5000), indicating the number of pieces in a line. The second line contains N integers Vi, volume of each piece (0 < Vi <=10^9). The third line contains N integers ai (0 < ai <=10000), and a1 is always 0.
The input is terminated by N = 0.
Output Output one line containing the minimum cost of all operations Xiaoji needs.
Sample Input 5 6 2 8 7 1 0 5 2 10 20 0
Sample Output 10
HintIn the sample, there is two ways to achieve Xiaoji’s goal. [6 2 8 7 1] -> [8 8 7 1] -> [8 8 8] will cost 5 + 5 = 10. [6 2 8 7 1] -> [24] will cost 20.
Author SYSU
Source 2014 Multi-University Training Contest 9
Recommend We have carefully selected several similar problems for you: 5431 5430 5429 5428 5427

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p]) 
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair 
#define MAXN (5000+10)
typedef __int64 ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int n,a[MAXN],v[MAXN];
ll s[MAXN],s2[MAXN];
int l[MAXN],r[MAXN],tot=0;
ll cost[MAXN];
int main()
{
// freopen("A.in","r",stdin);
// freopen(".out","w",stdout);

    while(scanf("%d",&n)&&n) {
        For(i,n) scanf("%d",&v[i]);
        For(i,n) scanf("%d",&a[i]); a[0]=0;
        s[0]=s2[n+1]=0;
        For(i,n) s[i]=s[i-1]+(ll)v[i];
        ForD(i,n) s2[i]=s2[i+1]+(ll)v[i];

        tot=0; 
        int fro=1,tail=n;
        while(fro<tail) {
            if (s[fro]==s2[tail]) {
                l[++tot]=fro;
                r[tot]=tail;
                fro++,tail--;
            } else if (s[fro]<s2[tail]) ++fro;
            else --tail;
        }
        MEMI(cost)
         l[0]=0,r[0]=n+1; cost[0]=0;
        ll ans=a[n];
        For(i,tot) {
            Rep(j,i) {
                cost[i]=min(cost[i],cost[j]+a[l[i]-l[j]]+a[r[j]-r[i]]);
            }           
            ans=min(ans,cost[i]+a[r[i]-1-l[i]]) ;       
        } 


        cout<<ans<<endl;
    } 


    return 0;
}