hdu 1085 Holding Bin-Laden Captive!，hdubin-laden
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 題目中說的問題是有1 2 5三中硬幣及其數量，問你用這些硬幣不能組成的最小數字是多少。一開始沒有思路，後來看了其他人的博客說用母函數，大概看了一下母函數的，本人也是初學母函數，這題算是母函數入門題，比較簡單，模擬多項式乘積就行，由於本人也是初學母函數，我在這就不介紹母函數了，網上好多資料，我覺得杭電的ppt比較好。 三種硬幣要組合起來可以看成是多項式相乘，比如一個價值為1的硬幣和一個價值為2的硬幣組合可以看成是（1+x）*（1+x^2）=1+x+x^2+x^3;每一項的指數代表組合後的價值，系數表示組成該價值的方法數。關鍵在於如何模擬多項式相乘。
![]()
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4
5 int main()
6 {
7 int n,m,k,a1[11000],a2[11000],a3[11000],ma;
8 while (cin>>n>>m>>k)
9 {
10 if (n==0&&m==0&&k==0)
11 break;
12 memset(a1,0,sizeof(a1));
13 memset(a2,0,sizeof(a1));
14 memset(a3,0,sizeof(a1));
15 for (int i=0;i<=n;i++)
16 a1[i]=1;
17
18 for (int j=0;j<=n;j++)
19 for (int i=0;i<=2*m;i+=2)
20 a2[j+i]+=a1[j];
21
22 for (int i=0;i<=n+2*m;i++)
23 for (int j=0;j<=k*5;j+=5)
24 a3[i+j]+=a2[i];
25
26 int t=0;
27 for (int i=0;i<=1100;i++)
28 {
29 if (a3[i]==0)
30 {
31 t=1;
32 cout <<i<<endl;
33 break;
34 }
35 }
36 if (t==0)
37 {
38 cout <<n+2*m+5*k+1<<endl;//這個地方要注意，所有的都有那就是n+2*m+5*k+1最小。
39 }
40 }
41 return 0;
42 }View Code
