最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。

久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。

现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，

每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。

当忍耐度降到0或者0以下时，xhd就不会玩这游戏。

xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？

​

​

思路

完全背包问题：

忍耐度m，杀怪数s

dp[m][s]表示在忍耐度为j，杀了k个怪的状态下所对应的经验值

AC代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 105;
int a[MAXN], b[MAXN]; //得到的经验值和会减掉的忍耐度
int dp[MAXN][MAXN]; //表示在忍耐度为j，杀了k个怪的状态下所对应的经验值

int main(){
    int n, m, k, s;//还需经验，忍耐度，怪的种数和最多的杀怪数
    while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF){
        for (int i = 0; i<k; i++)
            scanf("%d%d", &a[i], &b[i]);
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < k; i++)
            for (int j = b[i]; j <= m; j++)
                for (int k = 1; k <= s; k++)
                    dp[j][k] = max(dp[j][k], dp[j-b[i]][k-1]+a[i]);
        if(dp[m][s]>=n){
            for (int i = 1; i <= m; i++){
                if(dp[i][s]>=n){
                    printf("%d\n", m - i);
                    break;
                }
            }
        } else {
            printf("-1\n");
        }
    }
    return 0;
}