MYF

HDU 2159 FATE

Posted on | In | | Visitors

题目链接

HDU 2159

解题方法：动态规划(记录状态的完全背包)

题目分析

题目大意

输入n，m，k，s(0 < n,m,k,s < 100)四个正整数，分别代表xhd的升级所需经验、忍耐度、k种怪、最大打怪数量。每种怪有无限多只，问xhd能否升级，如果可以输出最大胜于忍耐度，否则输出－1。

解析

开一个二维数组dp[m+1][s+1]，dp[i][j]记录剩余耐力为i时打完第j个怪时获得的总经验。执行k次循环，每次取一个怪出来，j从最小可接受的忍耐度b[i]开始遍历，直到m，对于每一个忍耐度，记录在当前忍耐度下打p个怪时所获得的最大经验值dp[j][p]。

然后再搜索一遍dp数组，找到第一个dp[i][j]>=n，此时花费的忍耐度为i，剩余忍耐度为m-i；如果没有找到dp[i][j]>=n，则无解，输出-1。

代码

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
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define debug         printf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
int main(){
    int n,m,k,s;
    while (scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF) {
        int dp[110][110]={};
        int a[100]={};
        int b[100]={};
        for (int i=0; i<k; i++) {
            scanf("%d%d",&a[i],&b[i]);
        }
        
        for (int i=0; i<k; i++) {
            for (int j=b[i]; j<=m; j++) {
                for (int p=1; p<=s; p++) {
                    dp[j][p]=max(dp[j][p], dp[j-b[i]][p-1]+a[i]);
                }
            }
        }
        
        bool flag=false;
        for (int i=0; i<=m; i++) {
            for (int j=1; j<=s; j++) {
                if (dp[i][j]>=n) {
                    printf("%d\n",m-i);
                    flag=true;
                }
                if (flag) break;
            }
        }
        
        if (flag) continue;
        
        printf("-1\n");
    }
}