题目链接：点击打开链接
题目描述：现在有一群狼排成一条直线，，每匹狼有两个属性：ai表示自身的攻击力，bi表示协助相邻的狼时的攻击力；
杀死某匹狼时会受到这个狼自身的攻击和与它相邻的两匹狼的协助攻击。杀死某匹狼后，原来与这匹狼相邻的两匹狼
变成相邻的。问杀死所有狼所受的最小攻击是多少？
解题思路：区间dp
状态转移方程
dp[i][i]=a[i]+b[i-1]+b[i+1] //(i==j)（初始化一个点）dp[i][j]=min(a[i]+dp[i+1][j]+b[i-1]+b[j+1],a[j]+dp[i][j-1]+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]);//（合并两个区间）
代码：
#include <cstdio>#include <cstring>#include <iostream>#define MAXN 210using namespace std;int dp[MAXN][MAXN];int a[MAXN];int b[MAXN];int n;int main(){int T;scanf("%d",&T);for(int t=1;t<=T;++t){scanf("%d",&n);memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=1;i<=n;++i)scanf("%d",&a[i]);for(int i=1;i<=n;++i)scanf("%d",&b[i]);memset(dp,1,sizeof(dp));for(int i=1;i<=n;++i) dp[i][i]=a[i]+b[i-1]+b[i+1];for(int l=1;l<n;++l){for(int i=1;i+l<=n;++i){int j=i+l;dp[i][j]=min(a[i]+dp[i+1][j]+b[i-1]+b[j+1],a[j]+dp[i][j-1]+b[i-1]+b[j+1]);for(int k=i+1;k<j;++k){dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+a[k]+b[i-1]+b[j+1]);}}}printf("Case #%d: %d\n",t,dp[1][n]);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
人只要不失去方向，就不会失去自己
