P2998 [USACO10NOV] Candy S
题目描述
FJ 知道贝茜喜欢吃糖果。FJ 有N(1≤N≤40000)N (1 \le N \le 40000)N(1≤N≤40000)颗糖果，他想在若干天内将这些糖果送给贝茜。每一天，FJ 会让贝茜从他提供的一个列表中选择她当天想吃多少糖果，该列表有Nopt(1≤Nopt≤50)Nopt(1 \le Nopt \le 50)Nopt(1≤Nopt≤50)种不同的选项Ci(1≤Ci≤N)C_i (1 \le C_i \le N)Ci(1≤Ci≤N)。她必须恰好拿走CiC_iCi颗糖果。
农夫约翰给出了F(1≤F≤50)F(1 \le F \le 50)F(1≤F≤50)个他喜欢的数字FNi(1≤FNi≤N)FN_i (1 \le FN_i \le N)FNi(1≤FNi≤N)。每当一天结束时，如果剩余的糖果数量恰好等于这些数字之一，贝茜可以选择添加M（1≤M≤100)M（1 \le M \le 100)M（1≤M≤100)颗糖果。如果添加糖果后又出现了另一个 FJ 喜欢的数字，贝茜可能会再次获得添加MMM颗糖果的机会。在最好的情况下，贝茜可以获得无限多的糖果！
当贝茜无法在列表中选择糖果数量（因为糖果不够）时，她就无法再获得更多糖果。
不幸的是，贝茜不知道该如何规划才能吃掉尽可能多的糖果，所以她需要你的帮助。
举例来说，考虑以下场景：
- FJ 最初有101010颗糖果
- 贝茜每天可以选择吃掉333或555颗糖果
- 当剩余的糖果数量是222或444时，FJ 会添加111颗糖果
贝茜可以使用以下选择来最大化她能吃掉的糖果数量：
初始糖果数 吃掉糖果数 剩余糖果数 奖励糖果数 最终糖果数 第1天103707第2天73415第3天53213第4天33000输入格式
- 第111行：四个由空格分隔的整数：N,Nopt,F,MN,Nopt,F,MN,Nopt,F,M
- 第222行到第Nopt+1Nopt+1Nopt+1行：第i+1i+1i+1行包含一个整数：CiC_iCi
- 第Nopt+2Nopt+2Nopt+2行到第Nopt+F+1Nopt+F+1Nopt+F+1行：第i+Nopt+1i+Nopt+1i+Nopt+1行包含一个整数：FNiFN_iFNi
输出格式
- 第111行：一个整数，表示贝茜能吃掉的最大糖果数量，如果贝茜能吃掉无限多的糖果，则输出
-1。
输入输出样例 #1
输入 #1
10 2 2 1 3 5 4 2输出 #1
12C++实现
#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#definelllonglong#defineinf0x7f7f7f7f#defineN60usingnamespacestd;inlinellread(){ll x=0,f=1;charch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}returnx*f;}intn,nopt,F,m,c[N],f[N],book[40110],dp[40110],cnt[40110],ans;intmain(){n=read(),nopt=read(),F=read(),m=read();for(inti=1;i<=nopt;i++)c[i]=read();for(inti=1;i<=F;i++)book[read()]=1;memset(dp,-1,sizeof(dp));dp[n]=0;book[n]=false;for(inti=n;i;i--){if(dp[i]==-1)continue;if(cnt[i]>F+1)returnprintf("-1\n"),0;if(book[i]){cnt[i]++;if(dp[i]>dp[i+m]){dp[i+m]=dp[i];i+=m+1;}continue;}for(intj=1;j<=nopt;j++){if(i-c[j]<0)continue;dp[i-c[j]]=max(dp[i-c[j]],dp[i]+c[j]);}}for(inti=n;i>=0;i--)ans=max(ans,dp[i]);printf("%d\n",ans);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
