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;

}