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
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.
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.
5 6 2 8 7 1 0 5 2 10 20 0
10HintIn 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.
#include<stdio.h>
__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(i<j)
{
if(suml==sumr)
{
if(i+1<=j-1)dfs(i+1,j-1);
pre[l]=i; pre[j]=r;//区间最左最右块和相等
return ;
}
if(suml<sumr)suml+=v[++i];
else sumr+=v[--j];
}
pre[l]=r;//一个区间只能合成一块
}
void count(int k)//分成k个块后，从最中间块向两边扩大范围进行DP,pre[i]表示从第一块到
{
int l, r,m;
if(k%2)
{
l=k/2; r=k/2+2; m=k/2+1;//m是最中间块
dp[m]=a[pre[m]-pre[m-1]];
}
else
{
l=k/2; r=k/2+1; m=l; dp[l]=0;
}
while(r<=k)
{
dp[r]=a[pre[r]-pre[l-1]];//合成一大块时
for(int tr=r,tl=l;m<tr;tr--,tl++)//在区间块找出对应的最小dp[r]
if(dp[r]>dp[tr-1]+a[pre[r]-pre[tr-1]]+a[pre[tl]-pre[l-1]])
dp[r]=dp[tr-1]+a[pre[r]-pre[tr-1]]+a[pre[tl]-pre[l-1]];
l--;r++;//向两边扩增
}
}
int main()
{
int n,i,k;
__int64 tk;
while(scanf("%d",&n)>0&&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]);
}
}