自动搬运

查看原文

来自洛谷，原作者为

	L______ 生命流转，世俗交替；循环往复，六道轮回。

搬运于2025-08-24 21:44:15，当前版本为作者最后更新于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;
}