Holding Bin-Laden Captive!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 5966 Accepted Submission(s): 2607
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!
“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
题目大意为给你三种不同价值的硬币，分别为一、二、五，告诉你各自的数量，求由这些钱币所不能组成的最小财富这并不是连续的数值，所以在进行表达式的展开时，用的是数组，而不是小标 i 。
利用p[4]={0,1,2,5} 来存储 数值 ，num[4] 来存储对应数量，sum存储最大的财富值 其赋值为 sum=num[1]+2*num[2]+5*num[3],这样前期的工作就做好了，接下来就是 generating_function() 了。 有一点要注意就是 在判断不能组成财富的最下值是 界限不是sum而是sum+1，因为可能前面的都能组成，小心啊。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<time.h>
int n1[8005],n2[8005];
int num[4],p[4],sum;
void generating_function( )
{
memset(n1,0,sizeof(n1));
memset(n2,0,sizeof(n2));
n1[0]=1;
/* 初始化 ，这里 n1[0]=1 直接意义是总财富为零的组合方式是被接受的
即一个硬币都不放，尽管可能在某些题中不满足题意，但这个赋值是必要的
只有这样，后面的j=0时的判定才有意义，由于母函数主要是通过加法来
实现组合的存在性,在每次展开刚开始时，必定要求单纯的本身是存在的
n1[5]=1 ,代表 财富为5是可能的组合，现在当有一枚10元的硬币，那么
n1[15]=1，因为n1[5]=1 成立，15=10+5,所以后式，现在考虑刚开始处理
一枚 5 元的硬币，假设之前n1[5]=0, 那么如何使得 n1[5]=1成立呢 ，
显然 5=5+0; 所以n1[0]=1是有意义的。
*/
for(int i=1;i<=3;++i) // i从 1 开始很容易理解，因为我舍弃了num[0].
{
for(int j=0;j<=sum;++j)
// j从 1 开始呢，上面已经说明了原因 。
for(int k=0;k<=num[i]&&k*p[i]+j<=sum;++k)
// 我考虑过 k为什么从0开始，本来是这样想，
// 这种判定是否存在的题目可以直接从1开始，
// 我认为，如果取 k=0，那么 n2[k*p[i]+j]==n2[j]
// 后面又赋值给 n1[j] 不是多此一举吗，其实不是这样的
// 这个时候又要考虑到n1[0]这个特殊的例子了，如果k从1开始
// 那么一次n1与n2 之间的赋值后，则出现 n1[0]=0,着显然不行
if(n1[j])
n2[k*p[i]+j]=1;
for(int j=0;j<=sum;++j)
{
n1[j]=n2[j];
n2[j]=0;
}
}
}
int main()
{
p[1]=1,p[2]=2,p[3]=5;
while(scanf("%d%d%d",&num[1],&num[2],&num[3]),num[1]|num[2]|num[3])
{
sum=num[1]+2*num[2]+5*num[3];
generating_function( );
for(int i=0;i<=sum+1;++i) // 不是sum,而是sum+1.
if(n1[i]==0)
{
printf("%d\n",i);
break;
}
}
return 0;
}
直接的母函数题 WA 了很多次，真的很郁闷，很有必要从每一个小点对该算法的变形做下分析。