首页 > 代码库 > HDU5115 Dire Wolf (区间DP)
HDU5115 Dire Wolf (区间DP)
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=5115
题意:
有n只狼,每只狼有两种属性,一种攻击力一种附加值,我们没杀一只狼,那么我们受到的伤害值为
这只狼的攻击值与它旁边的两只狼的附加值的和,求把所有狼都杀光受到的最小的伤害值。
分析:
赤裸裸的区间DP
dp[i][j]表示把区间i,j内的所有狼杀光所受到的最小的伤害。
状态转移方程为
dp[i][j]=min{dp[i][k]+dp[k+1][j]-b[k]+b[i+1],dp[i][k]+dp[k+1][j]-b[k+1]+b[j+1]}(i<=k<j)这里讨论了先杀左边的还是先杀右边的
处理的时候要注意a[0],b[0],a[n+1],b[n+1]的初值都是0.
代码如下:
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxn = 210; int dp[maxn][maxn]; int a[maxn],b[maxn]; int main() { int n,t,cas=1; scanf("%d",&t); while(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]); a[0]=a[n+1]=0; b[0]=b[n+1]=0; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) dp[i][i]=a[i]+b[i-1]+b[i+1]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) dp[i][j]=999999999; for(int len = 2;len<=n;len++){ for(int i=1;i+len-1<=n;i++){ int j=i+len-1; for(int k=i;k<j;k++){ dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+b[i-1]-b[k]); dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+b[j+1]-b[k+1]); } } } printf("Case #%d: %d\n",cas++,dp[1][n]); } return 0; }
HDU5115 Dire Wolf (区间DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。