FATE
Problem Description
最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？
Input
输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)
Output
输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。
Sample Input
10 10 1 101 110 10 1 91 19 10 2 101 12 2
Sample Output
0-11
Author
Xhd
Source
题目类型：二维费用完全背包
算法分析：dp[j][q]表示杀前i种怪物且花费j个忍耐值，花费q个”怪物个数代价”所具有的最大经验值，这里将杀怪物的个数定义为一个代价。状态转移方程为dp[j][q] = max (dp[j][q], dp[j-c[i]][q-1] + w[i])。最后双重枚举找满足dp[i][j] >= n的最小的i。若没有，则直接输出-1，否则输出m - i
|
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
/************************************************* Author :supermaker Created Time :2015/11/22 15:49:21 File Location :C:\Users\abcd\Desktop\vim practice **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int aa[166], bb[166], dp[166][166]; int main() { //CFF; //CPPFF; int n, m, k, s; while (scanf ("%d %d %d %d", &n, &m, &k, &s) != EOF) { for (int i = 1; i <= k; i++) scanf ("%d %d", &aa[i], &bb[i]); memset (dp, 0, sizeof (dp)); for (int i = 1; i <= k; i++) { for (int j = bb[i]; j <= m; j++) { for (int q = 1; q <= s; q++) { dp[j][q] = max (dp[j][q], dp[j-bb[i]][q-1] + aa[i]); } } } int res = INF; for (int i = 1; i <= s; i++) { for (int j = 0; j <= m; j++) { if (dp[j][i] >= n) { res = min (res, j); } } } if (res == INF) puts ("-1"); else printf ("%d\n", m - res); } return 0; } |
- hdu1284：下一篇 »