题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1085

题目描述

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!

思路

这题也差不多,母函数为

$$G x=\left(1+x+x^2+\cdots+x^{\text{num$\_$} 1}\right)\cdot\left(1+x^2+x^4+\cdots+x^{2 \text{num$\_$} 2}\right)\cdot\\\left(1+x^5+x^{10}+\cdots+x^{5 \text{num$\_$} 5}\right)$$

展开后$x^i$的第一个系数为0即为最小不能凑出的价格$i$

AC代码

/*************************************************************************
    > File Name: 1085.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-06-30 Tue 22:41:48 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
const int _max = 9000;

int main()
{
#ifdef Oj
    // freopen(".in", "r", stdin);
#endif
    static int c1[_max+1], c2[_max+1];
    int num_1, num_2, num_5;
    while(cin >> num_1 >> num_2 >> num_5 && !(num_1==0 && num_2==0 && num_5==0)) {
        for(int i=0; i<=num_1; ++i) { // 1...num_1系数都为1,其余都为0
            c1[i] = 1;
            c2[i] = 0;
        }
        int N = num_1 + num_2*2 + num_5*5; // 所能凑成最大价值量 
        for(int i=num_1+1; i<=N+1; ++i) // 1...num_1系数都为1,其余都为0,小于等于N+1是为了方便最后的处理,即1-N都能凑成的话,那么N+1应该不能
            c1[i] = c2[i] = 0;
        for(int i=2; i<=3; ++i) { // 从第二个表达式开始往前合并,一共三个表达式
            for(int j=0; j<=N; ++j) {
                int l = 0; // l是用过当前硬币数量,每一次j更新都要归零
                for(int k=0;(k+j <= N)&& (i==2?l++<=num_2:l++<=num_5); k+=(i==2?2:5)) // l的大小应该小于总数量,或者$k+j\leq N$,这里会大于N是因为j从0-N。
                    c2[j+k] += c1[j];
            }
            for(int j=0; j<=N; ++j)  {
                c1[j] = c2[j];
                c2[j] = 0;
            }

        }
        for(int i=0; i<=N+1; ++i) { // 这里小于等于N+1省去了判断
            if(c1[i] == 0) {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}