這題是一個(gè)二維背包的題目，剛開(kāi)始并沒(méi)有那樣去做，只開(kāi)了一維的空間來(lái)存儲(chǔ)狀態(tài)，結(jié)果很多的數(shù)據(jù)都沒(méi)有跑過(guò)去。其實(shí)這題這樣來(lái)問(wèn)的話可能就明了很多了，求在指定的容忍值和指定的殺怪?jǐn)?shù)下，求最大能夠得到了經(jīng)驗(yàn)數(shù)，可能我們馬上就能想到二維背包，一維為殺怪?jǐn)?shù)，二維為容忍值，在做一個(gè)完全背包，可惜這題問(wèn)的是在滿足升級(jí)情況下最大的容忍值，這其實(shí)也能夠用上面構(gòu)建的模型了解決。只要的求解的過(guò)程每次將得到的經(jīng)驗(yàn)值與給定的N進(jìn)行比較，如果超過(guò)了N，那么說(shuō)明當(dāng)前的方案能夠觸發(fā)升級(jí)，再將此時(shí)剩余的容忍值傳遞出來(lái)就可以了。總而言之，題目對(duì)攻擊次數(shù)和容忍值進(jìn)行了限制，那么我們就要對(duì)限制的量進(jìn)行動(dòng)態(tài)規(guī)劃。

代碼如下：

#include <cstdlib> #include <cstring> #include <cstdio> #define MAXN 105 using namespace std;int N, M, K, S; int exp[MAXN], use[MAXN], dp[2500][2500];inline int max(int x, int y) {return x > y ? x : y; }int DP() {int flag = -1;for (int x = 1; x <= K; ++x) { for (int i = 1; i <= S; ++i) {for (int j = use[x]; j <= M; ++j) {dp[i][j] = max(dp[i-1][j-use[x]] + exp[x], dp[i][j]);if (dp[i][j] >= N) {flag = max(flag, M-j);}}}}return flag; }int main() {while (scanf("%d %d %d %d", &N, &M, &K, &S) == 4) {memset(dp, 0, sizeof (dp));for (int i = 1; i <= K; ++i) {scanf("%d %d", &exp[i], &use[i]);}printf("%d\n", DP());}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Lyush/archive/2012/04/21/2460976.html

總結(jié)

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

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