H - FATE（完全背包的变形问题）

﹏ヽ暗。殇╰゛Y 2022-02-24 10:40 182阅读 0赞

### 题目描述： ###

最近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 10  
1 1  
10 10 1 9  
1 1  
9 10 2 10  
1 1  
2 2

Sample Output  
0  
\-1  
1

##### 分析： #####

本题题意看着很是复杂。  
并且限制条件也多，所以有点难以入手。  
我们可以将k和m分别作为行，列下标。将整个问题先打包成一个完全背包的样子。  
然后， 题目要求是只要有n的经验值就可以了。所以，当每次求出dp\[j\]的时候，我们需要判断是不是〉=n，并且比之前>=n所花的空间少，还有他的怪的个数。  
前两个判断比较简单。 但是第三个判断需要借用一个辅助数组cnt。  
AC代码：

#include"stdio.h"
    #include"string.h"
    #include"functional"
    #include"iostream"
    #include"algorithm"
       using namespace std;
    typedef long long ll;
    #define scanll(a,b) scanf("%I64d%I64d",&a,&b);
    #define scanl(a) scanf("%I64d",&a);
    #define scanff(a,b) scanf("%lf%lf",&a,&b);
    #define scan1f(a) scanf("%lf",&a);
    #define prinll(a,b) printf("%I64d %I64d",a,b);
    #define prinl(a) printf("%I64d",a);
    #define printff(a,b) printf("%lf %lf",a,b);
    #define printlf(a) printf("%lf",a);
    #define OK printf("\n");
    #define MAXSIXE 310
    int main()
    {
        ll n,m,k,s;
        while(~scanf("%lld%lld%lld%lld",&n,&m,&k,&s))
        {
            ll p[110],w[110];
            for(ll i=1;i<=k;i++)
                scanll(p[i],w[i]);
            ll dp[110],cnt[110];
            memset(dp,0,sizeof(dp));
            memset(cnt,0,sizeof(cnt));
            ll ans=10000;
            for(ll i=1;i<=k;i++)
            {
                for(ll j=w[i];j<=m;j++)
                {
                    if(dp[j]<dp[j-w[i]]+p[i])
                      {//cnt数组保存到这个经验值，所需斩的怪兽的数量。
                          dp[j]=dp[j-w[i]]+p[i];cnt[j]=cnt[j-w[i]]+1;
                      }
                    if(dp[j]>=n&&ans>j&&cnt[j]<=s)
                    {
                        ans=j;
                    }
                }
            }
            printf("%lld\n",m-ans>=0?m-ans:-1);
        }
    }