HDOJ 5115 Dire Wolf
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5115
题目翻译
一行有(N)只狼，第(i)只狼有攻击力(A_{i})和攻击光环(B_{i})。当消灭一只狼的时候，主角会受到这只狼左右两只狼的攻击光环加成之后的这只狼的攻击力那么多的伤害，即(A_{i}+B_{i-1}+B_{i+1})。求如何使收到伤害最少然后消灭所有狼。
题解
区间DP。
DP[i][j]表示消灭区间i到j的狼所最少要受到的伤害。
转移的时候，我们就可以选择一匹狼，然后通过先消灭这匹狼左右的两个区间，再消灭这匹狼来转移到更大的区间。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
//while(true) RP++; #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int Maxn=200; int n; int attack[Maxn+5]; int protect[Maxn+5]; int DP[Maxn+5][Maxn+5]; inline void solve(int T){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&attack[i]); for (int i=1;i<=n;i++) scanf("%d",&protect[i]); int sum=0; for (int i=1;i<=n;i++) sum+=attack[i]; memset(DP,0,sizeof(DP)); for (int i=1;i<=n;i++) DP[i][i]=protect[i-1]+protect[i+1]; for (int len=2;len<=n;len++){ for (int left=1;left<=n;left++){ int right=left+len-1; if (right>n) break; DP[left][right]=DP[left+1][right]+protect[left-1]+protect[right+1]; for (int mid=left;mid<=right;mid++){ int now=DP[left][mid-1]+DP[mid+1][right]+protect[left-1]+protect[right+1]; if (DP[left][right]>now) DP[left][right]=now; } } } //for (int i=1;i<=n;i++) // for (int j=i;j<=n;j++) // printf("DP[%d][%d]=%d\n",i,j,DP[i][j]); printf("Case #%d: %d\n",T,sum+DP[1][n]); } int main(){ int T=0; while(scanf("%d",&T)!=EOF) for (int i=1;i<=T;i++) solve(i); return 0; } |
原文链接：HDOJ 5115 Dire Wolf
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!