【USACO】【数论】【DP】 Chapter 4 Section 1，1麦香牛块题解

题目

题目描述

农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看，”，奶牛们说，“如果你只用一次能装3块、6块或者10块的三种包装盒包装麦香牛块，你就不可能满足一次只想买1、2、4、5、7、8、11、14或者17块麦香牛块的顾客了。劣质的包装意味着劣质的产品。” 你的任务是帮助这些奶牛。给出包装盒的种类数N(1<=N<=10)和N个代表不同种类包装盒容纳麦香牛块个数的正整数(1<=i<=256)，输出顾客不能用上述包装盒(每种盒子数量无限)买到麦香牛块的最大块数。如果在限定范围内所有购买方案都能得到满足或者顾客不能买到的块数没有上限，则输出0。范围限制是所有不超过2,000,000,000的正整数。

输入

第1行: 包装盒的种类数N 第2行到N+1行: 每个种类包装盒容纳麦香牛块的个数

输出

输出文件只有一行数字：顾客不能用包装盒买到麦香牛块的最大块数或0(如果在限定范围内所有购买方案都能得到满足或者顾客不能买到的块数没有上限)。

样例输入

3
3
6
10

样例输出

17

First 普通完全背包

初看此题，题目中 每种盒子数量无限 提醒了我——这是一道背包题。
于是，在不到一分钟的时间内，我打完了代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int Maxn=10,Maxans=2000000000;
int n,w[Maxn+1];
bool dp[Maxans+1];
int main()
{#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&w[i]);dp[0]=1;for(int i=1;i<=n;i++)for(int j=w[i];j<=Maxans;j++)dp[j]|=dp[j-w[i]];int ans=-1;for(int i=Maxans;i>=1;i--)if(!dp[i]){ans=i;break;}if(ans==-1)printf("0\n");else printf("%d\n",ans);return 0;
}

但是，交上去后… …

我陷入了深深地沉思… …

NEXT 思考！

思考N久之后，我决定去网上搜。

我在网上搜了一下这道题。
但是，网上的都是用了这么一个神奇的结论：

若gcd(p,q)=1,则任意大于pq-p-q的数都能被p,q表示。

？？？
后来，我终于证到了。
具体过程如下：

设$px+qy=pq-p-q$,其中:$x\ge0$且$y\ge0$(很重要！！！)
则:$p(x+1)+q(y+1)=pq$
所以$p|y+1,q|x+1$
因为$p(x+1)\le pq,q(y+1)\le pq$
设:$x+1=kq$
代入得:$kpq+q(y+1)=pq$
整理得:$y+1=(1-k)p$
又因为:$k>0$且$x\ge0,y\ge0$
所以:$pq-p-q$不能用$px+qy$表示

我们得到了$pq-p-q$不能用$px+qy$表示
接下来，我们证明那一个神奇的结论：

设$n>pq-p-q$
则$(p-1)(q-1)=pq-p-q+1$
所以$n\ge(p-1)(q-1)$
因为$\gcd(p,q)=1$
则对于$z< \min(p,q)$存在$a$,$b$使$ap+bq=z$（可以通过扩展欧几里得算法得到）
不妨设$a>0>b$
显然$a>0$
若$a>q$:
设$a_1=a-q,b_1=b+p$
则有$a_1p+b_1q=z$
若$a_1>q$:
则可得到：$a_2p+b_2q=z$且$0<|a_2|<q,0<|b_2|<p$
设$n=pq-p-q+k\times\min(p,q)+r$
$r<z$
则取$A,B$使$Ap+Bq=r$且$0<|A|< q,0<|B|< p$
设$A>0$
则$n=pq-q-p+k\times\min(p,q)+r \\ =(q-1)p-p+k\times\min(p,q)+Ap+Bq\\ =(A-1)p+(B+q-1)p+k\times\min(p,q)$
其中$(A-1),(B+q-1)\ge0$
则无论$\min(p,q)$是$p$还是$q$，都有$n=pq-p-q+k\times\min(p,q)+r$
所以对于$n>pq-q-p$,都可以表示成$px+qy$

提示：可用扩展欧几里得算法证明！

FINALLY 正解

由上面的证明可知：

• 若每种包装盒装的个数不能够互质，所不能装的就没有上限，所以输出0
• 若能满足上一条件，就求背包容量
  
  • i从1循环到n
    
    • 将从1到i所有满足$\gcd(w[i],w[1...i])=1$的$lcm(w[i],w[1...i])$记录下来
• 在上面求出的所有数中取最小值，这就是容量
• 根据已求容量，做一次完全背包
• 在所求得的bool数组中，找出值为false的下标最大元素
• 若没有满足条件的元素，输出0，否则输出其下标

#include<cstdio>
const int Maxn=10,Maxans=2000000;
int n,w[Maxn+1];
int limit=1e9;
bool dp[Maxans+1];
int gcd(int a,int b)
{if(b==0)return a;return gcd(b,a%b);
}
int lcm(int a,int b)
{return a*b/gcd(a,b);
}
int main()
{#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&w[i]);int g=w[1];for(int i=1;i<=n;i++){g=gcd(g,w[i]);if(g==1)break;}if(g!=1){printf("0\n");return 0;}for(int i=1;i<=n;i++)for(int j=1;j<=i;j++){int t=lcm(w[i],w[j]);if(limit>t&&gcd(w[i],w[j])==1)limit=t;}dp[0]=1;for(int i=1;i<=n;i++)for(int j=0;j<limit;j++)if(dp[j])dp[j+w[i]]=1;int ans=-1;for(int i=0;i<limit;i++)if(!dp[i])ans=i;if(ans==-1)printf("0\n");else printf("%d\n",ans);
}

总结

这道题需要运用数论+DP的思想来做，就像NOIP2017第四题一样，需要各种算法综合运用。我们平时也需要这类方面的训练，而不要沉迷于某一种算法之中