http://acm.hdu.edu.cn/showproblem.php?pid=4960
给定一个长度为n的序列，然后再给出n个数bi,表示合成i个数的代价。每次可以将连续的子序列和成一个数，即为序列中各个项的和。要求将给定长度n的序列变成一个回文串，一个数字只能被合成一次。
先记录前i个的和和后n - j个和相同的(i,j)对，然后进行dp，dp[i]表示合并前i个和合并后n - g[i]个和合并所需最小代价，那么有递推公式dp[i] = min(dp[j] + b[i-j] + b[k - t]);
所求ans即为min(dp[i] + b[g[i] - i - 1]);
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include<set>
#include <iostream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d:%d",&x,&y)
#define clr0(x) memset(x,0,sizeof(x))
typedef long long LL;
#define N 10005
int n , m , K;
int a[N] , b[N];
LL sum[N];
int f[N] , g[N];void work(){int i , j , k , t;int ans;sum[0] = 0;a[0] = 0;for (i=1;i<=n;++i) scanf("%d",&a[i]) , sum[i] = sum[i-1] + a[i];for (i=1;i<=n;++i) scanf("%d",&b[i]); ans = b[n]; b[0] = 0;j = n;for (i=1;i<=n;++i){while (sum[n] - sum[j-1] < sum[i]) --j;if (sum[n] - sum[j-1] == sum[i])g[i] = j;else g[i] = -1;}memset(f,0x3f,sizeof(f));g[0] = n+1; f[0] = 0;for (i=1;i<=n;++i){if (g[i] == -1) continue;t = g[i];for (j=0;j<i;++j){if (g[j] == -1) continue;k = g[j];if (t <= i) continue;f[i] = min(f[i],f[j]+b[i-j]+b[k-t]);ans = min(ans,f[i]+b[t-i-1]);}}printf("%d\n",ans);
}int main(){while (~scanf("%d",&n) && n)work();return 0;
}
