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
思路
母函数或数学
开始一直不太懂j和k到底什么意思，多做几道慢慢有点感觉
多刷题…
母函数
/*************************************************************************
> File Name: hdu1085_1.cpp
> Author:gens_ukiy
> Mail:
> Created Time: 2016年11月30日 星期三 12时39分32秒
************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 8005
int c1[maxn],c2[maxn];
int main(){
int coin[3]={1,2,5};
int num[3];
while(cin>>num[0]>>num[1]>>num[2]){
memset(c1,0,sizeof(c1));
memset(c2,0,sizeof(c2));
if(!num[0]&&!num[1]&&!num[2])break;
int sum=num[0]+num[1]*2+num[2]*5;
for(int i=0;i<=num[0];i++)
c1[i]=1;
int k,k1;
for(int i=1;i<=2;i++)
{
for(int j=0;j<=sum;j++)
for(k=0,k1=0;k1<=num[i];k+=coin[i],k1++)
c2[j+k] += c1[j];
for(int j=0;j<=sum;j++)
c1[j]=c2[j],c2[j]=0;
}
for(int i=1;;i++){
if(c1[i]==0)
{
printf("%d\n",i);
break;
}
}
}
}
数学
数学没学好,学统计学,统计学没学好，学计算机Orz…,but 计算机没学好呢…
/*************************************************************************
> File Name: hdu1085.cpp
> Author:gens_ukiy
> Mail:
> Created Time: 2016年11月30日 星期三 00时15分32秒
************************************************************************/
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int n1,n2,n3;
while(cin>>n1>>n2>>n3){
if(!n1&&!n2&&!n3) break;
if(n1==0) printf("1\n");
else
{
if(n1+2*n2<4)
printf("%d\n",n1+2*n2+1);
else
printf("%d\n",5*n3+n1+2*n2+1);
}
}
}