题意

思路：

length less~larger

dp[i][j] = min(dp[i][j],dp[i][k - 1] +dp[k +1][j] + a[k] + b[i - 1] +b[j + 1]);

qaq看注释吧 

ACcode 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>using namespace std;
const int inf = 0x3f3f3f3f;int t,n;
int a[205],b[205];
int dp[205][205];int main()
{scanf("%d",&t);for(int T = 1;T <= t; T++){scanf("%d",&n);for(int i = 1;i <= n; i++) scanf("%d",&a[i]);for(int i = 1;i <= n; i++) scanf("%d",&b[i]);b[n + 1] = 0,b[0] = 0;//边界memset(dp,0,sizeof dp);//为了后续取min 可能会调用dp[x][x - 1]for(int i = 1;i <= n; i++){for(int j = i;j <= n; j++){dp[i][j] = inf;}}for(int len = 1;len <= n; len++){for(int i = 1;i + len - 1 <= n;i++){int j = len + i - 1;for(int k = i;k <= j; k++){//why not ->for(int k = i + 1;k < j; k++) ????//because:when(len == 1){dp[x][x]始终等于inf没有更新;}dp[i][j] = min(dp[i][j],dp[i][k - 1] + dp[k + 1][j] + a[k] + b[i - 1] + b[j + 1]);//why(a[k] + b[i - 1] + b[j + 1])?//dp[i][k - 1] and dp[k + 1][j]是两个已经消灭得知cost的区间 即died wolves}}}printf("Case #%d: %d\n",T,dp[1][n]);}
}