给定一个长度为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#include #include #include #include #include #include #include #include #include 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 10005int 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