题目链接：点击这里

题意：把一个数列合并成回文序列，每一个数字只能和并一次，只能连续的子串进行合并，合并后的数字是他们的和，花费是他们中数字个数的函数。给出原始串和花费函数求最小的花费。

$O(n)$扫一遍相等的前缀的后缀，$dp_i$表示i下标和对应下标的后缀合并之后的最小花费，那么 $$dp_i=min\left\{ dp_j+cost(i,j-1)\big\|i\leq j \right\}$$

#include <bits/stdc++.h>
using namespace std;
#define maxn 5005
int n;
int a[maxn];
int v[maxn];
int x[maxn], y[maxn];
long long dp[maxn];
long long sumx[maxn];
long long sumy[maxn];
int main () {//freopen("1.txt","r",stdin);while(scanf("%d",&n)&&(n!=0)) {sumx[0] = 0, sumy[n+1] = 0;for (int i = 1; i <= n; i++)scanf("%d", &a[i]), sumx[i] = sumx[i-1]+a[i];for (int i = n; i >= 1; i--) sumy[i] = sumy[i+1]+a[i];for (int i = 1; i <= n; i++)scanf ("%d", &v[i]);int L = 1, R = n, tt = 0;while (L <= R+1) {if (sumx[L-1] == sumy[R+1]) {x[++tt] = L, y[tt] = R;L++, R--;}while (L <= R+1 && sumx[L-1] < sumy[R+1]) L++;while (L <= R+1 && sumx[L-1] > sumy[R+1]) R--;}for (int i = tt; i >= 1; i--) {dp[i] = v[y[i]-x[i]+1]; //不断开for (int j = i+1; j <= tt; j++) {int num_l = x[j]-x[i], num_r = y[i]-y[j];dp[i] = min (dp[i], dp[j]+v[num_l]+v[num_r]);}}printf ("%lld\n", dp[1]);}return 0;
}