题目：

Another OCD Patient

  
5
6 2 8 7 1
0 5 2 10 20
0

  
10
Hint
In 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.
 

题意：给n个数字，可以把连续的数字合并成一个数字，合并连续X个数字需要cost【X】花费，求把这n个数字转化为回文序列所需的最小花费。

思路：由于最后需要转化成回文序列，我们可以从两端开始模拟，如果左边的数小于右边的数，那么左边加上下一个数，如果左边大于右边，那么右边加上下一个数，直到二者相等，那么这部分就作为一个整体，分别记录下左边和右边合并了多少数字。假设最后左右各有len个部分，但这len个部分还可以从两端或中间合并来得到更小的花费，所以我们dp一下，dp【i】为左右对称前i个部分合并的最小代价，那么dp【i】=min(,dp【j】+cost【左边j到i 部分合并的个数】+cost【右边j到i 部分合并的个数】)，这是从两端的最小花费。从中间合并的时候，分别减去两端合并的个数，再加上中间合并的花费就行了。

代码：

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include<climits>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;#define PB push_back
#define MP make_pair#define REP(i,x,n) for(int i=x;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define FORD(i,h,l) for(int i=(h);i>=(l);--i)
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define OI(X) printf("%d",X);
#define RS(X) scanf("%s", (X))
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define Swap(a, b) (a ^= b, b ^= a, a ^= b)
#define Dpoint  strcut node{int x,y}
#define cmpd int cmp(const int &a,const int &b){return a>b;}/*#ifdef HOMEfreopen("in.txt","r",stdin);#endif*/
const int MOD = 1e9+7;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
//#define HOMEint Scan()
{int res = 0, ch, flag = 0;if((ch = getchar()) == '-')				//判断正负flag = 1;else if(ch >= '0' && ch <= '9')			//得到完整的数res = ch - '0';while((ch = getchar()) >= '0' && ch <= '9' )res = res * 10 + ch - '0';return flag ? -res : res;
}
/*----------------PLEASE-----DO-----NOT-----HACK-----ME--------------------*/int a[5005];
int cost[5005];
int dp[5005];
int ll[5005];
int rr[5005];
int main()
{ int n;
while(RI(n)!=EOF)
{   if(!n)
break;for(int i=1;i<=n;i++)RI(a[i]);for(int i=1;i<=n;i++)RI(cost[i]);int len=0;for(int i=1,j=n;i<j;i++,j--){long long int lsum=a[i];long long int rsum=a[j];int lnum=1;int rnum=1;while(lsum!=rsum){if(lsum<rsum){lsum+=a[++i];lnum++;}else{rsum+=a[--j];rnum++;}}if(lsum==rsum){len++;ll[len]=lnum;rr[len]=rnum;}}dp[0]=0;for(int i=1;i<=len;i++){dp[i]=INT_MAX;int lt=0,rt=0;for(int j=i;j>=1;j--){  lt+=ll[j];rt+=rr[j];dp[i]=min(dp[i],dp[j-1]+cost[lt]+cost[rt]);}}int ans=cost[n];for(int i=1;i<=len;i++){n-=ll[i]+rr[i];ans=min(ans,dp[i]+cost[n]);}printf("%d\n",ans);}return 0;
}