传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5115

森林狼嘛，1费11但是可以给相邻的随从加buff，hhh

现在有一列森林狼，你需要A死他们，当然你也会受到伤害每一只森林狼有自己的攻击力a[i]，以及对相邻的加成b[i]，当一只森林狼挂掉后两边的即成相邻

求消耗最少的血量

区间DP

设f[i][j]为i~j消耗的血量，

f[i][j]=min(f[i][k]+f[k+1][j]+a[k])+b[i-1]+b[j+1] (i<k<j)

这样只能处理区间长度>=3的情况，对于长度=1或=2的情况需要预处理出来

代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>using namespace std;int T;int n;int a[205],b[205];int f[205][205];int main()
{scanf("%d",&T);for (int t=1;t<=T;t++){memset(a,0,sizeof(a));memset(b,0,sizeof(b));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]);}for (int i=1;i<=n;i++){f[i][i]=a[i]+b[i-1]+b[i+1];}for (int l=2;l<=n;l++){for (int i=1;i+l-1<=n;i++){int j=l+i-1;f[i][j]=min(f[i+1][j]+a[i],f[i][j-1]+a[j]);for (int k=i+1;k<j;k++){f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+a[k]);}f[i][j]+=b[i-1]+b[j+1];}}printf("Case #%d: %d\n",t,f[1][n]);}return 0;
}