HDU4960Another OCD Patient（區間dp,分塊後再DP）

Another OCD Patient

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 716 Accepted Submission(s): 270


Problem Description Xiaoji is an OCD (obsessive-compulsive disorder) patient. This morning, his children played with plasticene. They broke the plasticene into N pieces, and put them in a line. Each piece has a volume Vi. Since Xiaoji is an OCD patient, he can't stand with the disorder of the volume of the N pieces of plasticene. Now he wants to merge some successive pieces so that the volume in line is symmetrical! For example, (10, 20, 20, 10), (4,1,4) and (2) are symmetrical but (3,1,2), (3, 1, 1) and (1, 2, 1, 2) are not.

However, because Xiaoji's OCD is more and more serious, now he has a strange opinion that merging i successive pieces into one will cost ai. And he wants to achieve his goal with minimum cost. Can you help him?

By the way, if one piece is merged by Xiaoji, he would not use it to merge again. Don't ask why. You should know Xiaoji has an OCD.
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 題意：給出n個數，把這n個數合成一個對稱的集合。第三行代表一次合成i個數需要花費a[i]，求出最小的花費。 解題：先把n個數合成一個對稱集合共k個塊，再進行對稱區間DP。

#include
__int64 v[5005],a[5005],pre[5005],dp[5005];
void dfs(int l,int r)//分塊，使[l,r]對稱
{
    int i=l,j=r;
    __int64 suml=v[l],sumr=v[r];
    while(i0&&n)
    {
        for( i=1;i<=n;i++)scanf("%I64d",&v[i]);
        for( i=1;i<=n;i++)scanf("%I64d",&a[i]);
        dfs(1,n);
        k=0; i=1;pre[0]=0;
        while(i<=n)//把一整塊縮成一個點，pre[k]變成前k個塊共有多少個數組成k塊
        {
            tk=pre[i]-i+1; i=pre[i]+1; ++k; pre[k]=tk+pre[k-1];
        }
        count(k);
        printf("%I64d\n",dp[k]);
    }
}