程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1085 Holding Bin-Laden Captive!(母函數)

hdu 1085 Holding Bin-Laden Captive!(母函數)

編輯：C++入門知識

hdu 1085 Holding Bin-Laden Captive!(母函數)

題意：1元，2元，5元的硬幣分別有num[1],num[2],num[3]個。問用這些硬幣不能組合成的最小錢數。

繼續母函數。

有兩個注意的地方：

對c2[]初始化的同時也要對c1[]初始化。

最後枚舉到sum+1，因為存在[1,sum]都可以湊成的可能，這時輸出sum+1。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;

int c1[8010],c2[8010];
int add[4] = {0,1,2,5};
int num[4];

int main()
{
	while(~scanf(%d %d %d,&num[1],&num[2],&num[3]))
	{
		if(num[1] == 0 && num[2] == 0 && num[3] == 0)
			break;

		int sum = num[1] + num[2]*2 + num[3]*5; //可以到達的最高錢數
		memset(c2,0,sizeof(c2));
		memset(c1,0,sizeof(c1));

		for(int i = 0; i <= num[1]; i++)
		{
			c1[i] = 1;
		}

		for(int i = 2; i <= 3; i++)
		{
			for(int j = 0; j <= sum; j++)
			{
				for(int k = 0; k+j <= sum && k <= add[i]*num[i]; k += add[i])
				{
					c2[k+j] += c1[j];
				}
			}
			for(int j = 0; j <= sum; j++)
			{
				c1[j] = c2[j];
				c2[j] = 0;
			}
		}

		for(int i = 1; i <= sum+1; i++) //注意枚舉到sum+1,因為若[1,sum]都可以湊成的話，應該輸出sum+1.
		{
			if(c1[i] == 0)
			{
				printf(%d
,i);
				break;
			}
		}
	}
	return 0;
}