哪里找多校联合训练解题报告？——杭电ACM微博~

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 12176    Accepted Submission(s): 5457 Problem Description We all know that Bin-Laden is a notorious terrorist, and he has disappeared for a long time. But recently, it is reported that he hides in Hang Zhou of China!  “Oh, God! How terrible! ” Don’t be so afraid, guys. Although he hides in a cave of Hang Zhou, he dares not to go out. Laden is so bored recent years that he fling himself into some math problems, and he said that if anyone can solve his problem, he will give himself up!  Ha-ha! Obviously, Laden is too proud of his intelligence! But, what is his problem? “Given some Chinese Coins (硬币) (three kinds-- 1, 2, 5), and their number is num_1, num_2 and num_5 respectively, please output the minimum value that you cannot pay with given coins.” You, super ACMer, should solve the problem easily, and don’t forget to take $25000000 from Bush!   Input Input contains multiple test cases. Each test case contains 3 positive integers num_1, num_2 and num_5 (0<=num_i<=1000). A test case containing 0 0 0 terminates the input and this test case is not to be processed.   Output Output the minimum positive value that one cannot pay with given coins, one line for one case.   Sample Input 1 1 3 0 0 0   Sample Output 4   Author lcy

至于理解可参考：

http://jijiwaiwai163.blog.163.com/blog/static/186296211201181794138746/

/*
 * Author:  *****
 * Created Time:  2013/8/9 20:10:49
 * File Name: hblc.cpp
 * solve: hblc.cpp
 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<iostream>
#include<vector>
#include<queue>

using namespace std;
#define sz(v) ((int)(v).size())
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repf(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define clr(x) memset(x,0,sizeof(x))
#define clrs( x , y ) memset(x,y,sizeof(x))
#define out(x) printf(#x" %d\n", x)
#define sqr(x) ((x) * (x))
typedef long long LL;

const int INF = -1u>>1;
const double eps = 1e-8;
const int maxn = 8001;

int sgn(const double &x) {  return (x > eps) - (x < -eps); }

int ans[maxn];
int temp[maxn];
int num[6];
int cnt[4];

int main() 
{
   //freopen("in.txt","r",stdin);
    
    int num1,num2,num5;
    while(scanf("%d%d%d",&num1,&num2,&num5)==3)
    {
        if(num1 == 0 && num2 == 0 && num5 == 0)
            break;

        int sum = num1 + num2*2 + num5*5;

        memset(ans,0,sizeof(ans));
        memset(temp,0,sizeof(temp));

        cnt[1] = num1;
        cnt[2] = num2;
        cnt[3] = num5;

        for(int i = 0;i<=cnt[1];++i)
        {
            ans[i] = 1;
        } 

        num[1] = 1;
        num[2] = 2;
        num[3] = 5;

        for(int i = 2;i<=3;++i)
        {
            for(int j = 0;j<=sum;++j)
            {
                for(int k = 0;k*num[i]+j<=sum && k<=cnt[i];k++)
                {
                    temp[k*num[i]+j] += ans[j];
                }
            }

            for(int j = 0;j<=sum;++j)
            {
                ans[j] = temp[j];
                temp[j] = 0;
            }
        }

        for(int i = 1;i<=sum+1;++i)
            if(ans[i] == 0)
            {
                cout<<i<<endl;
                break;
            }

    } 
    return 0;
}

描述：以这个题为例子，简单描述下母函数吧、

举个例子。
若有1克、2克、3克、4克的砝码各一 枚，能称出哪几种重量？各有几种可能方案？
分析：
如何解决这个问题呢？考虑构造母函数。 
如果用x的指数表示称出的重量，则： 
1个1克的砝码可以用函数1+x表示， 
1个2克的砝码可以用函数1+x2表示， 
1个3克的砝码可以用函数1+x3表示， 
1个4克的砝码可以用函数1+x4表示
几种砝码的组合可以称重的情况，可以用以上几个函数的乘积表示：
(1+x)(1+x2)(1+x3)(1+x4) 
=(1+x+x2+x3)(1+x3+x4+x7) 
=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10  
从上面的函数知道：可称出从1克到10克，系数便是方案数。 
例如右端有2x5 项，即称出5克的方案有2：5=3+2=4+1；同样，6=1+2+3=4+2；10=1+2+3+4。 
故称出6克的方案有2，称出10克的方案有1 

应该有个理解了吧。前面还有那个整数划分，也可用母函数解决。

这道题的意思就是：给你面值是1，2，5的硬币的数量，要你求由这些硬币不能组成的最小的金额。。
分析：

如果叫你写由面值1,2,5的硬币所组成的金额的母函数，如下：
Y=(1+x^2+x^3+x^4…+x^n1*1)*(1+x^2+x^4+x^6…x^n2*2)*(1+x^5+x^10+…x^n3*5)

先分开描述下：（易于理解）

#include <iostream>
#include <stdio.h>
using namespace std;
int c1[10000],c2[10000];
int main()
{
 int i,j,k;
 int a,b,c;
 int sum=0;
 while(scanf("%d%d%d",&a,&b,&c)!=EOF)
 {
  if(a==0&&b==0&&c==0)break;
  sum=a+b*2+c*5;
  for(i=0;i<sum;i++)
  {
   c1[i]=0;
   c2[i]=0;
  }
  for(i=0;i<=a;i++)           //第一个表达式。。（1+x^2+x^3+x^4…+x^n1*1）都取一个。。
   c1[i]=1;
  for(i=0;i<=a;i++)           //先是面值1，和面值2，的硬币的母函数,。。就是第一个表达式乘第二个表达式；i控制的是第一个表达式指数。。j是第二个表达式的指数。。
   for(j=0;j<=b*2;j+=2)     //j+=2..就是上面的Y=（）（）（）的第一式子。。这样比较好理解
    c2[i+j]+=c1[i];             //这步就是把指数相同的合并在一起，也就是把指数相同的系数相加。。[i+j]就是指数。。
   for(i=0;i<=a+b*2;i++)
   {
    c1[i]=c2[i];               //把c2的赋值给c1.。
    c2[i]=0;
   }
   for(i=0;i<=a+b*2;i++)
    for(j=0;j<=c*5;j+=5)   //和上面类似。。
     c2[i+j]+=c1[i];
    for(i=0;i<=a+b*2+c*5;i++)
    {
     c1[i]=c2[i];
     c2[i]=0;
    }
    for(i=0;i<=sum;i++)
    {
     if(c1[i]==0)
     {
      cout<<i<<endl;
      break;
     }
    }
    if(i==sum+1)
     cout<<i<<endl;
 }

 return 0;
}

合并起来：

#include <stdio.h>
#include <string.h>
int a[8001],b[8001];
int c[]={1,2,5};
int main()
{
    int i,j,k,n[3],s;
    while(scanf("%d%d%d",&n[0],&n[1],&n[2])!=EOF,n[0]+n[1]+n[2])
    {
        s=n[0]*1+n[1]*2+n[2]*5;
        if(n[0]==0)
   printf("1\n");
        else
        {
   memset(a,0,sizeof(a));
   memset(b,0,sizeof(b));
            for(i=0;i<=n[0];i++)
                  a[i]=1;
            for(i=1;i<3;i++)
            {
    for(j=0;j<=s;j++)
                    for(k=0;k*c[i]+j<=s&&k<=n[i];k++)                   //k*c[i]+j<=s总的金额不能超过最大。k<=n[i] K是使用相应面值的数量 因此不能超过给定的上限 就是程序对应输入值    
                        b[k*c[i]+j]+=a[j];                 
     for(j=0; j<=s; j++)
     {
      a[j]=b[j];
      b[j]=0;
     }
            }
            for(i=0; i<=s+1; i++)
                if(a[i]==0)
    {
     printf("%d\n",i);
     break;
    }
        }
    }
    return 0;
}