[洛谷 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;
}