题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5115
题目大意：
有一些狼，从左到右排列，每只狼有一个伤害A，还有一个伤害B。杀死一只狼的时候，会受到这只狼的伤害A和这只狼两边的狼的伤害B的和。
若两只狼之间的狼都被杀了，这两只狼也算相邻。求杀掉一排狼的最小代价。
解题思路：
设dp[i][j]为消灭编号从i到j只狼的代价，那么结果就是dp[1][n]
枚举k作为最后一只被杀死的狼，此时会受到a[k]和b[i-1] b[j+1]的伤害 取最小的即可。
可列出转移方程：dp[i][j]=min(dp[i][j], dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1])
dp[i][i]=a[i]+b[i-1]+b[j+1];
开始还是没有想明白，枚举k的意义是什么，结果把状态转移方程写错了。
代码：
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<string>
#define lc(a) (a<<1)
#define rc(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define _for(i,start,end) for(int i=start;i<=end;i++)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const int N=1e3+;
const int INF=0x3f3f3f3f;
const double eps=1e-; int a[N],b[N];
int dp[N][N]; int main(){
FAST_IO;
int t,cas=;
cin>>t;
while(t--){
memset(dp,,sizeof(dp));
memset(b,,sizeof(b));
int n;
cin>>n;
for(int i=;i<=n;i++){
cin>>a[i];
}
for(int i=;i<=n;i++){
cin>>b[i];
}
for(int i=;i<=n;i++){
dp[i][i]=a[i]+b[i-]+b[i+];
}
for(int len=;len<n;len++){
for(int i=;i+len<=n;i++){
int j=i+len;
dp[i][j]=INF;
//枚举k作为最后一只被杀死的狼
for(int k=i;k<=j;k++){
dp[i][j]=min(dp[i][j],dp[i][k-]+dp[k+][j]+a[k]+b[i-]+b[j+]);
}
}
}
printf("Case #%d: %d\n",++cas,dp[][n]);
}
return ;
}