题解 P2737 【[USACO4.1]麦香牛块Beef McNuggets】
楼下都能证明上界，然后都用类似完全背包的做法。这里我提供一种不同的思路。
题目大意为数组中取数，每个数取任意多次，问不能凑出来的最大数。
容易yy出来，如果一个数k可以被凑出来，那么对于物品大小为x，k+x，k+2x，k+3x……都可以凑出来。
那么我们不妨对所有能凑出来的方案对任意一个物品x取模，分成0到x-1一共x组。
我们现在要求出每一组方案的最小值。
然后在每一组方案的最小值里取最大值，减去x，即为答案。
为什么呢？
假设每一组能凑到的方案的最小值的最大值为t，由于这个t在这一组里是最小值，那么t-x一定不能凑出来。否则t就不是最小值了。
而且由于t在所有的组中是最大值，假设t=ax+b，那么ax+0，ax+1，ax+2………ax+x-1也可以被凑出来，这x个数是其他组别里的方案或者其他组别里的方案加上整数个x得到的。但是，t-x即ax+b-x不能被凑出来（因为t是最小值），而上面的ax+y中，y如果小于b，要么ax+y可以凑出，那么对答案没影响，要么ax+y减去任意个x可以被凑出，但是肯定小于t-x；y如果大于b，那么ax+y-x一定可以凑出，否者ax+y>t，不符合条件，所以也不是最优解。
表述不是很明了，不如探讨样例。
选择3作为x，
除以3余0的方案 最小值是0（什么都不选）
除以3余1的方案 最小值是10 选一个10
除以3余2的方案 最小值是20 选两个10
那0 3 6 9 12 15 18 21……都可以由第一组的0加任意个3凑出；
10 13 16 19 22 25……都可以由第二组的10加任意个3凑出；
20 23 26 29 32 35……都可以由第三组的20加任意个3凑出。
我们发现上面的20，21，22三个数连续了，也就是这个剩余系完整了，那么大于22的数一定全都可以有这三个数加3凑出来。
但是20前面有缺的，即20-3=17，20-2*3，20-3*3……一定凑不出来。
对于10和0也同理。
所以这些凑不出来的数里面最大的肯定就是最大的20只减去一个3，也就是17。
那么如何求出每一组的最小值呢？
这里就是本题的精华所在，也就是最短路模型的转化。
我们不妨把0到x-1建立x个点，对于每一个点，我们枚举题目给出的a[i]，从x到(x+a[i])%x连一条边权为a[i]的边，表示(ax+b)%x加上a[i]变成了(ax+b+a[i])%x。
然后0的距离是0，也就是什么都不取。
从0开始跑单源最短路。
假如跑完以后出现某个点的距离减去x大于题目的上界，那么就输出0；
假如某个点到达不了，那么显然也输出0，因为这表示这一组的方案一定是凑不出来的。
排除以上可能后，假如最大距离是0，那么输出0，因为这表示所有的数都可以凑出来。
对于这个x的选择，当然是任意的，但是x的大小即为点的个数，所以x不妨选最小的那个（然而x要保证非0）。
这题因此可以用dij写，然而数据不大，所以spfa也可以0ms过掉。
复杂度上界Θ(n*n*min(i))
以下是本蒟蒻丑陋无比的代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define UPPER 2000000000
typedef long long LL;
LL dis[400],val[10000],a[20],mx=-1,mn=400;
int q[10000],head,tail,used[400],n,point[10000],yest[10000],last[400],total;
void adde(int f,int t,int v){
//cout<<"add"<<f<<"->"<<t<<" "<<v<<endl;
point[++total]=t;
val[total]=v;
yest[total]=last[f];
last[f]=total;
}
void spfa(int p){
memset(dis,-1,sizeof(dis));
dis[p]=0;
used[p]=1;
head=tail=1;
q[1]=p;
int f,t,v;
while(head<=tail){
f=q[head];
//cout<<"f="<<f<<endl;
for(int i=last[f];i;i=yest[i]){
t=point[i];
//cout<<f<<"->"<<t<<" "<<val[i]<<endl;
if(dis[t]==-1||dis[f]+val[i]<dis[t]){
dis[t]=dis[f]+val[i];
if(!used[t]){
used[t]=1;
q[++tail]=t;
}
}
}
used[f]=0;
head++;
}
}
int main(){
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(mn>a[i]) mn=a[i];
}
for(int i=0;i<mn;i++)
for(int j=1;j<=n;j++)
adde(i,(i+a[j])%mn,a[j]);
spfa(0);
int flag=1;
for(int i=0;i<mn;i++){
if(dis[i]==-1||dis[i]-mn>UPPER){
flag=0;
break;
}
else{
if(dis[i]>mx) mx=dis[i];
}
}
if(!flag) puts("0");
else{
if(mx-mn>=0) printf("%lld\n",mx-mn);
else puts("0");//这里我也是后来想到的，因为mn最小，那么不可能有任何方案比mn更小，除非这个mx=0，这样才能mx-mn<0
}
return 0;
}