USACO Section 4.1 Beef McNuggets - 描述真吓人~

     坑爹的描述说最大可能到2*10^9....我开始推的时候就推出最大只会到65535...还犹豫了好久~~结果用这个算法就过了~~最大的也就是65535...数据范围真心好吓人阿...

     这道题很简单的说...首先看要输出0的情况...

          1.没有得不到的数...那显然只有最小的盒子为1才行..特判就行了..

          2.得不到的数是无穷的.恰恰是这个地方给了我解题的灵感...首先..给出的盒子整数倍肯定都能覆盖到..那么覆盖不到的只能是非盒子的整数倍..但这些非整数倍又能给互相消化掉...如有2,3...2的整数倍为2,4,6,8,...而3的为3,6,9,12....这里如2覆盖不到的3,5,7,9,11..可以和3来配合覆盖...但有时候配合也配合不出..那么就只能说有无穷多个覆盖不到了..这里找出容量最小的盒子..若1~( 最小盒子容量-1 ) 都能以各种组合来完成..就说明了不能覆盖到的个数是有限的...

          再看一下样例...3,6,10...答案是17...17是怎么来的...最小的盒子是3..那么要能覆盖到1,2才能说覆盖不到的个数是有限...而6%3==0..也就是说6与3配合无论怎么配合..除3余1和余2的个数是组合不出来的...如果10和3来组合..首先10%3==1..而且两个10..20%3==2...这里就能说明覆盖个数是有限的...这里的17就是=20-3...因为在20之前..所有除3余2的数都无法覆盖...所以这里就是20-3=17了...17之后所有的数都能组合出来..

          思路理清了就用背包来解了~~~

Program:

/*
ID: zzyzzy12
LANG: C++
TASK: nuggets
*/
#include<iostream>
#include<istream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stack>
#include<algorithm>
#include<queue>
#define oo 2000000000
#define ll long long
#define pi (atan(2)+atan(0.5))*2
using namespace std;
int n,a[11];
void getanswer()
{
int dp[300],i,j,k,ans;
if (a[1]==1) goto A;
for (i=1;i<=256;i++) dp[i]=oo;
dp[0]=0;
for (i=2;i<=n;i++)
{
k=a[i]%a[1];
if (!k) continue;
for (j=0;j<=a[1];j++)
if (dp[(j+k)%a[1]]-a[i]>dp[j])
dp[(j+k)%a[1]]=dp[j]+a[i];
}
ans=0;
for (i=1;i<a[1];i++)
{
if (dp[i]==oo)
{
A:
printf("0\n");
return;
}
if (dp[i]>ans) ans=dp[i];
}
printf("%d\n",ans-a[1]);
}
int main()
{
freopen("nuggets.in","r",stdin);
freopen("nuggets.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
getanswer();
return 0;
}