题解 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)) 以下是本蒟蒻丑陋无比的代码 ```cpp #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; } ```