题解 P2998 【[USACO10NOV]糖果Candy】

L______ · 2019-10-20 21:14:11 · 题解

看到这种类型的问题基本上就是什么可反悔的贪心或者是dp之类的了。

最开始想了一下是不是可以用堆维护然后可反悔的贪心，但是发现想不出来（事实上是因为我太菜了），就开始想dp思路。

首先我们可以考虑，当不存在可以加糖的情况时，我们以dp[i]表示当剩余糖的个数为i时最多可以吃掉的糖的数量。于是可以很轻松地推出状态转移方程

dp[i-c[j]]=max(dp[i-c[j]],dp[i]+c[j]);

其中c[j]为题目给出的每次可以选择吃掉的糖的数量。

但是题目中给出当存在i为一个fj喜欢的数的时候时是可以加入m个糖的，那么i+m以后的状态都有可能受到影响，那么该怎么办呢？

很简单，我们如果正常枚举状态是从n枚举到1，对于一个i下一个枚举的状态就是i-1，假如i为fj喜欢的数,那么就把i加上m+1，于是我们下一个枚举的状态就会从i+m开始了（总感觉有点小暴力但是时间复杂度什么的蒟蒻我又不会证）

用cnt[i]记录到达每个状态的次数，然后就可以判断是否可以无限吃糖的情况了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define inf 0x7f7f7f7f
#define N 60
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int n,nopt,F,m,c[N],f[N],book[40110],dp[40110],cnt[40110],ans;

int main(){
    n=read(),nopt=read(),F=read(),m=read();
    for(int i=1;i<=nopt;i++) c[i]=read();
    for(int i=1;i<=F;i++) book[read()]=1;
    memset(dp,-1,sizeof(dp));
    dp[n]=0;book[n]=false;
    for(int i=n;i;i--){
        if(dp[i]==-1) continue;
        if(cnt[i]>F+1) return printf("-1\n"),0;
        if(book[i]){
            cnt[i]++;
            if(dp[i]>dp[i+m]){
                dp[i+m]=dp[i];
                i+=m+1;
            }
            continue;
        }
        for(int j=1;j<=nopt;j++){
            if(i-c[j]<0) continue;
            dp[i-c[j]]=max(dp[i-c[j]],dp[i]+c[j]);
        }
    }
    for(int i=n;i>=0;i--) ans=max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}