杭电 HDU ACM 1085 Holding Bin-Laden Captive!

cbam 2021-09-01 原文

Holding Bin-Laden Captive!

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16548 Accepted Submission(s): 7436

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 3

0 0

Sample Output

4

Author

lcy

学完母函数后亲手做出来的第一个，所以说只有真正理解算法的含义才会把他敲出来并根据题目具体要求学会灵活便通过。同样是写出母函数表达式，然后三重循环，把多项式乘开，判断哪个指数从0增大过程中，哪一项的系数为0。此项即为所求，但有一处wa特别厉害好几次，每次初始化两个数组的时候，一定要把保存最终系数结果的数组的最后下标值加一的的元素置为0；

#include<iostream>
const int M=100000;
#include<algorithm>
using namespace std;
int main()
{
    int i,j,k,n1,n2,n5,cnt[M],dic[M];//cnt 标记 系数  dic 记录每项指数
    while(cin>>n1>>n2>>n5,n1+n2+n5)
    {
        int Min=n1+2*n2+5*n5; //能够出现的最高次幂
        for(int h=0; h<=Min; h++)
        {
            cnt[h]=1;
            dic[h]=0;
        }
        cnt[Min+1]=0;
  // 计算前两大项乘开之后的结果
        for(j=0; j<=n1; j++)//循环第一项中各项
            for(k=0; k<=2*n2; k+=2)
            {
                dic[j+k]+=cnt[j];//j+k为相乘过程中出现的系数 cnt为上一大项的结果 和这个乘完之后的叠加
            }
        for(int p=0; p<=2*n2+n1; p++)
        {
            cnt[p]=dic[p];cnt//保留当前最终系数结果 即前两大项乘完之后的结果
            dic[p]=0;
        }

        for(j=0; j<=2*n2+n1; j++)
            for(k=0; k<=5*n5; k+=5)
            {
                dic[j+k]+=cnt[j];
            }
        for(int  e=0; e<=Min; e++)
        {
            cnt[e]=dic[e];
            dic[e]=0;

        }
        for(int q=0;; q++)
        {
            if(!cnt[q])
            {
                cout<<q<<endl;
                break;
            }

        }
    }
    return 0;
}