FATE

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)


Problem Description 最近xhd正在玩一款叫做FATE的游戲，為了得到極品裝備，xhd在不停的殺怪做任務(wù)。久而久之xhd開始對殺怪產(chǎn)生的厭惡感，但又不得不通過殺怪來升完這最后一級。現(xiàn)在的問題是，xhd升掉最后一級還需n的經(jīng)驗(yàn)值，xhd還留有m的忍耐度，每殺一個(gè)怪xhd會(huì)得到相應(yīng)的經(jīng)驗(yàn)，并減掉相應(yīng)的忍耐度。當(dāng)忍耐度降到0或者0以下時(shí)，xhd就不會(huì)玩這游戲。xhd還說了他最多只殺s只怪。請問他能升掉這最后一級嗎？
Input 輸入數(shù)據(jù)有多組，對于每組數(shù)據(jù)第一行輸入n，m，k，s(0 < n,m,k,s < 100)四個(gè)正整數(shù)。分別表示還需的經(jīng)驗(yàn)值，保留的忍耐度，怪的種數(shù)和最多的殺怪?jǐn)?shù)。接下來輸入k行數(shù)據(jù)。每行數(shù)據(jù)輸入兩個(gè)正整數(shù)a，b(0 < a,b < 20)；分別表示殺掉一只這種怪xhd會(huì)得到的經(jīng)驗(yàn)值和會(huì)減掉的忍耐度。(每種怪都有無數(shù)個(gè))
Output 輸出升完這級還能保留的最大忍耐度，如果無法升完這級輸出-1。
Sample Input 10 10 1 10 1 1 10 10 1 9 1 1 9 10 2 10 1 1 2 2
Sample Output 0 -1 1先求出不超過他的忍耐度殺完s只怪時(shí)能夠得到的經(jīng)驗(yàn)值， 如果能升完最后一級，再求用去多少忍耐度就能夠升級，最后用他的忍耐度減去需要消耗的忍耐度即可 /*忍耐度當(dāng)做體積，經(jīng)驗(yàn)值當(dāng)做價(jià)值，怪的只數(shù)當(dāng)做物品數(shù)量*/狀態(tài)轉(zhuǎn)移方程：f[i][j]=max{f[i][j],f[i-b][j-1]+a} i表示忍耐度，j表示殺怪?jǐn)?shù)代碼：/*忍耐度當(dāng)做體積，經(jīng)驗(yàn)值當(dāng)做價(jià)值，怪的只數(shù)當(dāng)做物品數(shù)量*/ #include<stdio.h> #include<string.h> int dp[105][105],a[105],b[105]; int max(int a,int b) {return a>b?a:b; } int main() {int i,j,k,n,m,K,s;while(scanf("%d%d%d%d",&n,&m,&K,&s)!=EOF){for(i=0;i<K;i++)scanf("%d%d",&a[i],&b[i]);memset(dp,0,sizeof(dp));for(i=0;i<K;i++) //控制第幾組for(j=b[i];j<=m;j++) //控制忍耐度for(k=1;k<=s;k++) //控制殺怪只數(shù)dp[j][k]=max(dp[j][k],dp[j-b[i]][k-1]+a[i]);//不殺這只怪之前的經(jīng)驗(yàn)值加上殺了之后的經(jīng)驗(yàn)值，所以k-1if(dp[m][s]>=n){for(i=0;i<=m;i++) //尋找能夠升級所消耗的最小忍耐度,只用找消耗相同忍耐度的情況下，令殺怪?jǐn)?shù)量最多，if(dp[i][s]>=n) //dp[i][s]是消耗i忍耐度的情況下，獲得的最大經(jīng)驗(yàn)值{printf("%d\n",m-i); //求剩余的忍耐度break;}}elseprintf("-1\n"); //不能升級}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 2159 FATE 二维背包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。