首页 > 代码库 > Hdu5115 Dire Wolf
Hdu5115 Dire Wolf
Hdu5115 Dire Wolf
http://acm.hdu.edu.cn/showproblem.php?pid=5115
题目大意：n头狼，分别有一个攻击力，而且分别有一个加持力，可以给左右两边的狼加相应的攻击力（边界的狼就只能给相邻的一头狼加） ，一个人要杀狼，杀一头狼时受到该狼的攻击力和来自周围的加持力。被杀死的狼的加持力消失，但其他狼又会更新加持力（因为相邻的位置变化了）。问该人能够把全部狼杀光，且最小受到多少伤害？
/* dp[i][j]表示从第i头狼到第j头狼全部被杀死的最小伤害 dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+v[k]+w[i-1]+w[j+1]);*/#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;int T,w[220],v[220],n,dp[220][220];int main(){ scanf("%d",&T); for(int o=1;o<=T;o++){ memset(dp,127/3,sizeof(dp)); memset(v,0,sizeof(v)); memset(w,0,sizeof(w)); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&v[i]); for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1;i<=n;i++)dp[i][i]=v[i]+w[i-1]+w[i+1]; for(int i=n-1;i>=1;i--){ for(int j=i+1;j<=n;j++){ dp[i][j]=min(dp[i+1][j]+v[i]+w[i-1]+w[j+1],dp[i][j-1]+v[j]+w[j+1]+w[i-1]); for(int k=i+1;k<=j-1;k++) dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+v[k]+w[i-1]+w[j+1]); } } printf("Case #%d: %d\n",o,dp[1][n]); }}
Hdu5115 Dire Wolf
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。