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;     
}