항 저 우 전기 hdu 2069 Coin Change 모 함수

1009 단어 모 함수
http://acm.hdu.edu.cn/showproblem.php?pid=2069
모 함수 문 제 는 정말 넓 고 심오 하 다. 동전 의 수량 을 제한 할 때 또 새로운 시련 이 생 겼 다.이 문 제 는 어떻게 제한 합 니까?깊이 생각해 야 지.
#include 
#include 

#define MAX 251

int c1[MAX][101], c2[MAX][101];

int res[MAX];

int num[6] = {0, 1, 5, 10, 25, 50};

void init()
{
	int i, j, k, p;
	memset(c1, 0, sizeof(c1));
	memset(c2, 0, sizeof(c2));
	c1[0][0] = 1;
	for(i = 1; i <= 5; i ++){
		for(j = 0; j < MAX; j ++){//     250
			for(k = 0; k*num[i]+j < MAX; k ++){
				for(p = 0; p + k <= 100; p ++){//         100?
					c2[k*num[i]+j][p + k] += c1[j][p];
				}
			}
		}
		for(j = 0; j < MAX; j ++){
			for(k = 0;  k < 101; k ++){
				c1[j][k] = c2[j][k];
				c2[j][k] = 0;
			}
		}
	}
	for(i = 1; i < MAX; i ++){
		for(j = 1; j < 101; j ++){
			res[i] += c1[i][j];
		}
	}
	res[0] = 1;
}

int main()
{
	int n;
	init();
	while(scanf("%d", &n)!=EOF){
		printf("%d
", res[n]); } return 0; }

좋은 웹페이지 즐겨찾기