항 저 우 전기 hdu 2069 Coin Change 모 함수
1009 단어 모 함수
모 함수 문 제 는 정말 넓 고 심오 하 다. 동전 의 수량 을 제한 할 때 또 새로운 시련 이 생 겼 다.이 문 제 는 어떻게 제한 합 니까?깊이 생각해 야 지.
#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;
}