本文主要是介绍HDU 2159 FATE（二维dp背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个题由于变量比较多。 所以容易搞复杂。 其实看明白了 还是一个背包问题。
但是这个明显就是 一种怪可以打很多个了。
有一个细节需要注意。被这个细节坑了一发。 那就是 当 它的 经验超过n的时候 也是可以升级的。 比如 经验需要3 有一种 可以得到经验2 的怪。 那就必须杀两个得到4个经验
才能升级。 而我第一次写的代码就是 只判断了 3的情况。 所以就错了。我往后推了一步。因为经验最多就是20. 那我 直接得出 n----n+20之间的所有情况就好了
递推公式比较好写。 我用 d【i】【j】 表示 i经验 j个怪的时候 所能用的最小忍耐度。
不过A了之后 去看别人写的题解。 发现 用 d【i】【j】 表示 i 忍耐度 j个怪的时候 如果经验 大于等于 n的时候 就是最优解。 这个好像更简单 更好理解
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <fstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cmath>
#include <iomanip>
#include <cmath>
typedef long long LL;
typedef unsigned long long LLU;
const double PI=acos(-1.0);
using namespace std;
#define MAXN 100+21
#define INF 1 << 30
int d[MAXN][MAXN] = {0};
struct Game{int v;int de;
};
int main (){int n,m,k,s;while(scanf("%d%d%d%d",&n,&m,&k,&s) != EOF){for(int i = 0; i < MAXN; i++){for(int j = 0 ;j < MAXN; j++)d[i][j] = INF;}Game g[MAXN];for(int i = 1; i <= k; i++)scanf("%d%d",&g[i].v,&g[i].de);d[0][0] = 0;for(int i = 0; i <= n+20; i++){for(int j = 1; j <= s; j++){for(int z = 1; z <= k; z++){if(i-g[z].v >= 0 && d[i-g[z].v][j-1]+g[z].de <= m && d[i-g[z].v][j-1] != INF)d[i][j] = min(d[i][j],d[i-g[z].v][j-1]+g[z].de);}}}int M = INF;for(int j = n; j <= n+20; j++){for(int i = 0; i <= s; i++)M = min(M, d[j][i]);}if(M > m)printf("-1\n");elseprintf("%d\n",m-M);}return 0;
}
这篇关于HDU 2159 FATE（二维dp背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
