链接：点击打开链接

题意：有一排狼，每只狼有一个伤害A，还有一个伤害B。杀死一只狼的时候，会受到这只狼的伤害A和这只狼两边的狼的伤害B的和。如果某位置的狼被杀，那么杀它左边的狼时就会收到来自右边狼的B，因为这两只狼是相邻的了。求杀掉一排狼的最小代价。

代码：

#include<stdio.h>
#include<cstring>
#include<iostream>
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3f;
long long a[205],b[205],dp[205][205];
int main(){long long t,n,i,j,k,l,cas;scanf("%I64d",&t);for(cas=1;cas<=t;cas++){scanf("%I64d",&n);for(i=1;i<=n;i++)for(j=1;j<=n;j++)dp[i][j]=INF;for(i=1;i<=n;i++)scanf("%I64d",&a[i]);for(i=1;i<=n;i++)scanf("%I64d",&b[i]);for(i=1;i<=n;i++)dp[i][i]=a[i]+b[i-1]+b[i+1];for(i=1;i<n;i++){                       dp[i][i+1]=min(dp[i][i+1],a[i]+b[i-1]+b[i+1]+a[i+1]+b[i-1]+b[i+2]);dp[i][i+1]=min(dp[i][i+1],a[i+1]+b[i]+b[i+2]+a[i]+b[i-1]+b[i+2]);}for(l=3;l<=n;l++){                      //遍历所有的顺序，也就是分成for(i=1;i<=n-l+1;i++){              //三部分后的顺序j=i+l-1;                        dp[i][j]=min(dp[i][j],dp[i][i]+dp[i+1][j]-b[i]+b[i-1]);dp[i][j]=min(dp[i][j],dp[i][i]+dp[i+1][j]-b[i+1]+b[j+1]);dp[i][j]=min(dp[i][j],dp[i][j-1]+dp[j][j]-b[j-1]+b[i-1]);dp[i][j]=min(dp[i][j],dp[i][j-1]+dp[j][j]-b[j]+b[j+1]);for(k=i+1;k<=j-1;k++){          //其实可以把k当作最后一个被攻击的目标也就不用这么麻烦了dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][k]+dp[k+1][j]-b[k-1]+b[i-1]-b[k]+b[i-1]);dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][k]+dp[k+1][j]-b[k-1]-b[k+1]+b[i-1]+b[j+1]);dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][k]+dp[k+1][j]-b[k]+b[k+1]-b[k]+b[i-1]);dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][k]+dp[k+1][j]-b[k]-b[k]+b[k-1]+b[j+1]);dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][k]+dp[k+1][j]-b[k+1]-b[k-1]+b[i-1]+b[j+1]);dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k][k]+dp[k+1][j]-b[k+1]-b[k]+b[j+1]+b[j+1]);}}}printf("Case #%I64d: %I64d\n",cas,dp[1][n]);}return 0;
}