usaco training 4.1.1 麦香牛块 题解

Farmer Brown‘s cows are up in arms, having heard that McDonalds is considering the introduction of a new product: Beef McNuggets. The cows are trying to find any possible way to put such a product in a negative light.

One strategy the cows are pursuing is that of `inferior packaging‘. ``Look,‘‘ say the cows, ``if you have Beef McNuggets in boxes of 3, 6, and 10, you can not satisfy a customer who wants 1, 2, 4, 5, 7, 8, 11, 14, or 17 McNuggets. Bad packaging: bad product.‘‘

Help the cows. Given N (the number of packaging options, 1 <= N <= 10), and a set of N positive integers (1 <= i <= 256) that represent the number of nuggets in the various packages, output the largest number of nuggets that can not be purchased by buying nuggets in the given sizes. Print 0 if all possible purchases can be made or if there is no bound to the largest number.

The largest impossible number (if it exists) will be no larger than 2,000,000,000.

PROGRAM NAME: nuggets

INPUT FORMAT

OUTPUT FORMAT

       真的是数学不行啊，开始认为背包一定不行，因为要搜到20亿才能判断。走投无路下查看了相关的题解，发现枚举的范围是很小的一个数，即背包是可行的！

       通过深入研究，我总结了以下的思路。

       ①我们先来证明为什么出解范围为什么可以<=256^2.有数论知识“有两个数p,q,且gcd(q,p)=1,则最大无法表示成px+qy（x>=0,y>=0)的数是pq-q-p”（证明可以参见http://blog.csdn.net/archibaldyangfan/article/details/7637831）因为题目中的数据都是小于等于256的，所以如果有最大无法表示的数，必然小于256^2（我们甚至可以抹去后面的减法）。

       ②那么，就可以采用构造法了，最坏复杂度是（256^2)*10。 

    对于无限解：

• 如果输入数据中有1，为无限解。
• 如果某个大于256^2的数不能被合成，为无限解。并且可以证明，这个数字一定小于等256^2+256。

   一个不专业的证明：设x是1~256^2中最大的一个能被合成的数，y是min(data[i])（输入数据中最小的一个），易知x+min(q[i])-1不能被合成（由于没有1）。

   ③DP的优化（大牛无视此段）

      ------开始的时候我的DP竟然连样例都超时！

一开始的核心代码：

 memset(f,0,sizeof(f));
  f[0]=true;now=0;
  for (i=1;i<=n;i++)
  {
    for (j=0;j<=now;j++)
      if (f[j])
      {
        k=1;
        while (j+k*a[i]<=maxn)
        {
          f[j+k*a[i]]=true;
          k++;
        }
        k--;
        now=(j+k*a[i]>now)?(j+k*a[i]):now;
      }
  }

 仔细一想，其实对于这个n^3的DP，有很多重复的点取处理了。我们可以采用无限背包的思想来解决。

以下是详细的AC代码：

/*
{
ID:juan1973
LANG:C++
PROG:nuggets
}
*/
#include<stdio.h>
#include<cstring>
using namespace std;
const int maxn=256*256;
const int maxx=256*256+256;
bool f[maxx+1],flag; 
int nn,i,j,n,c,a[11],now,k;
int main()
{
  freopen("nuggets.in","r",stdin);
  freopen("nuggets.out","w",stdout);
  scanf("%ld",&nn);n=0;
  for (i=1;i<=nn;i++) 
  {
    scanf("%ld",&c);
    if (c==1) 
    {
      printf("0\n");
      return 0;
    }
    flag=true;
    for (j=1;j<=n;j++)
      if (c%a[j]==0) {flag=false;break;}
    if (flag) a[++n]=c;
  }
  memset(f,0,sizeof(f));
  f[0]=true;
  for (i=1;i<=n;i++)
    for (j=a[i];j<=maxx;j++)
      if (f[j-a[i]]) f[j]=true;
  for (i=maxx;i>maxn;i--) if (!f[i]) {printf("0\n");return 0;}
  for (i=maxn;i>0;i--)
    if (!f[i])
    {
      printf("%ld\n",i);
      return 0;
    }
  printf("0\n");
  return 0;
}

usaco training 4.1.1 麦香牛块 题解

原文：http://blog.csdn.net/jiangshibiao/article/details/19915537