太弱了打了一年这种题还做不出来。。。
dp[i][j] = min(dp[i][j],dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1]) k:i->j;
dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1] 的理解是先把k左边的区间消掉再把k右边的点消掉，最后消灭k，当消灭k时因为两边都没了所以受i-1和j+1两个点影响所以加
b[i-1]+b[j+1]+a[k]

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
int a,b[500];
LL dp[205][205];
LL dfs(int l,int r)
{if(l>r)return 0;if(dp[l][r]!=-1)return dp[l][r];LL res = 99999999999;for(int i=l;i<=r;i++)res = min(res,dfs(l,i-1)+dfs(i+1,r));dp[l][r] = res+b[l-1]+b[r+1];return dp[l][r];
}
int main()
{int t,i1 = 1,n;scanf("%d",&t);while(t--){scanf("%d",&n);LL ans = 0;memset(dp,-1,sizeof(dp));for(int i=1;i<=n;i++){scanf("%d",&a);ans+=a;}for(int i=1;i<=n;i++)scanf("%d",&b[i]);LL ans1 = dfs(1,n);printf("Case #%d: ",i1);i1++;printf("%I64d\n",ans+ans1);}return 0;
}