这一题要注意利用数列对称的性质，即v[1]+v[2]+..+v[i]和v[j]+v[j+1]+..+v[N]的点，两个对称点之间合并的代价只能是a[j-i+1]，dp[i][j]表示将[i,j]区间内的数列合并到对称形式的最小代价，因此状态转移方程是dp[i][j]=min(dp[i][j],a[x-i+1]+a[r-j+1]+dp[i+1,j-1])，这里面[x,y]包含于[i,j]区间，即=[i,j]区间向内合并到对称点，再由对称点合并到最终状态。
我本来想写递推的，结果蒟蒻写晕了==，因为这里状态转移的方向一个index向前一个index向后==然后就写了好久没写的记忆化搜索，注意搜索时要对非法情况(l,r)越界的特判。
感觉这种数列的DP都是考虑区间状态的转移，然后是二维DP。。(⊙v⊙)
至于找到对称点，直接头指针向尾跑，尾指针向头跑挨个判断就行了。
Plus，开始没注意前缀和会超long long，因此WA了好久。。。(⊙o⊙)…
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
#include<map>
#include<time.h>
using namespace std;
//hdu 4960
const int maxn=5010;
int N;
int v[maxn];
int a[maxn];
int dp[maxn][maxn];
pair<int,int> p[maxn];
int cnt;
void found2()//别人的做法
{
memset(dp,-1,sizeof(dp));
memset(p,0,sizeof(p));
long long sum[maxn];
memset(sum,0,sizeof(sum));
for(int i=1;i<=N;i++) sum[i]=sum[i-1]+v[i];
cnt=1;
int w=1;
for(int q=N;q>=1;q--)
{
while(w<q&&sum[w]-sum[0]<sum[N]-sum[q-1])w++;
if(w==q)break;
if(sum[w]-sum[0]==sum[N]-sum[q-1])
{
p[cnt++]=make_pair(w,q);
}
}
// for(int i=0;i<=cnt-1;i++)
// {
// cout<<p[i].first<<" "<<p[i].second<<endl;
// }
}
void found()
{
memset(dp,-1,sizeof(dp));
memset(p,0,sizeof(p));
int i=1;
int j=N;
long long s[maxn];//注意s[i]最大是5K*1W会超int，之前把这个写成了intWA了好久，比对别人的code才发现==怎么又犯这个错了==
memset(s,0,sizeof(s));
s[i]=v[1];
s[N]=v[N];
cnt=1;
p[0]=make_pair(1,N);
//cout<<N<<endl;
while(i<j)
{
//cout<<i<<" "<<j<<" "<<s[i]<<" "<<s[j]<<endl;
if(s[i]==s[j])
{
p[cnt++]=make_pair(i,j);
i++;
j--;
s[i]=v[i]+s[i-1];
s[j]=v[j]+s[j+1];
}
else if(s[i]<s[j])
{
i++;
s[i]=v[i]+s[i-1];
}
else if(s[i]>s[j])
{
j--;
s[j]=v[j]+s[j+1];
}
}
}
int dfs(int l,int r,int dep)
{
if(dp[l][r]!=-1) return dp[l][r];
if(l>=r) return dp[l][r]=0;//非法情况判定
dp[l][r]=a[r-l+1];//该区间最坏情况一个一个合并，要合并r-l+1次
for(;dep<cnt;dep++)
{
int x=p[dep].first;
int y=p[dep].second;
//cout<<x<<" "<<y<<endl;
dp[l][r]=min(dp[l][r],a[x-l+1]+a[r-y+1]+dfs(x+1,y-1,dep+1));//dp[l][r]+
}
return dp[l][r];
}
void DP()//please ignore it
{
int x=p[cnt-1].first;
int y=p[cnt-1].second;
dp[x][y]=0;
for(int i=cnt-2;i>=0;i--)
{
x=p[i].first;
y=p[i].second;
for(int j=cnt-1;j>i;j--)//WA 不能只计算对称点，要计算区间内的所有点。
{
int xx=p[j].first;
int yy=p[j].second;
dp[x][y]=min(dp[x][y],dp[xx][yy]+a[xx-x+1]+a[y-yy+1]);
}
}
printf("%d\n",dp[1][N]);
}
int main()
{
freopen("input.txt","r",stdin);
// freopen("data.txt","r",stdin);
// freopen("out1.txt","w",stdout);
while(scanf("%d",&N)!=EOF)
{
if(N==0) break;
memset(v,0,sizeof(v));
memset(a,0,sizeof(a));
for(int i=1;i<=N;i++)
{
scanf("%d",&v[i]);
}
for(int i=1;i<=N;i++)
{
scanf("%d",&a[i]);
}
found();
//DP();
printf("%d\n",dfs(1,N,1));
}
return 0;
}