[洛谷 2737]Beef McNuggets

题目链接

https://www.luogu.org/problem/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;
}

发表回复

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据