首页 > ACM题库 > HDU-杭电 > HDU 1085 Holding Bin-Laden Captive!-组合数学-[解题报告] C++
2013
11-27

HDU 1085 Holding Bin-Laden Captive!-组合数学-[解题报告] C++

Holding Bin-Laden Captive!

问题描述 :

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 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 the minimum positive value that one cannot pay with given coins, one line for one case.

样例输入:

1 1 3
0 0 0

样例输出:

4

此题在前题1082上增加了些变化,硬币的个数有限。指数的范围变成不确定,最大可能为sum=a[0]+a[1]*2+a[2]*5。第3层循环控制硬币的个数。另外,j是第一个括号的指数,虽然第1趟时j<=a[0],但其它趟可能超过,故上限为sum。c1的初始化也得注意,因为1元硬币只有a[0]个,所以只有a[0]个c1[i]=1。

AC代码:

//1398 16:07
#include<iostream>
using namespace std;
const int iNum=8005;
int c1[iNum],c2[iNum];
int main()
{
	int n,i,j,k,sum;
	int elem[3]={1,2,5};
	int a[3];
	while (cin>>a[0]>>a[1]>>a[2]){
			if(a[0]==0&&a[1]==0&&a[2]==0)
				break;
			if(a[0]==0){
				printf("1\n");
				continue;
			}
			sum=a[0]+a[1]*2+a[2]*5;//有可能达到的指数的上限
			for (i=0;i<=iNum;i++){//c1保存第1个括号,c2总是保存一趟运算的结果(每一对括号合并成一个括号)  
				c1[i]=0;
				c2[i]=0; 
			} 

			for (i=0;i<=a[0];i++)//此题1元硬币只有a[0]个
				c1[i]=1;  
			for (i=1;i<=2;i++){//n个括号要进行n-1趟运算				
				for (j=0;j<=sum;j++)//j是第一个括号的指数,虽然第1趟时j<=a[0],但其它趟可能超过,故上限为sum  
					for (k=0;k*elem[i]+j<=iNum&&k<=a[i];k++){//k是第i种硬币的个数,k*elem[i]才是第二个括号的指数  
						c2[j+k*elem[i]]+=c1[j];//第二个括号的系数都是1,隐含了c2[j+k]+=c1[j]*1; 
					} 
				for (j=0;j<=iNum;j++){//c1保存第1个括号,要保存成前一趟运算的结果
					c1[j]=c2[j];
					c2[j]=0;
				}  
			}  
			for(i=0;i<=iNum;i++){
				if(c1[i]==0){
					printf("%d\n",i);
					break;
				}

			}
	}
	return 0;
}


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测