[洛谷 2737]Beef McNuggets

题目链接

https://www.luogu.org/problemnew/show/P2737

题解

第一眼看到这道题的时候:我去,这不就是小凯的疑惑嘛!

这让我想起了NOIp2018上同样的场景。当我看到货币系统的时候,也想到了\(exgcd\)。

然而事实是残酷的。(因为我们可以拿三种以上的货币组成新货币)

好了,我们接下来进入正题。

虽然本题的解法并非\(exgcd\),但这道题在\(n=2\)的特例,即两个互质数\(p,q\)的自然数倍之和,所不能表示的最大数字为\(p*q-p-q\)的结论,还是有些帮助的。

这道题和货币系统的相似之处就是,它们都可以用背包的方法做出来。

因为数字的上限为256,所以我们枚举的上限也就是\(256^2-256*2+1=65025\)。(不懂的话再翻回去看一下结论吧)

#include <cstdio>
#include <algorithm>
#define MAXANS 65025
using namespace std;
int a[15],f[70005];
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  scanf("%d",&a[i]);
 f[0]=1;
 for(int i=1;i<=n;i++)
  for(int j=1;j<=MAXANS;j++)
   if(j-a[i]>=0&&f[j-a[i]])f[j]=1;
 for(int i=MAXANS;i>0;i--)
  if(!f[i])
  {
   if(i<=MAXANS-1)printf("%d\n",i);
   else break;
   return 0;
  }
 puts("0");
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注