HDU 2069 Coin Change 母函数求解

题目：?pid=2069

这题比普通的母函数求解题目复杂一点，多了组成个数的限制，要求组合个数不能超过 100 个硬币，所以将 c1, c2 定义为二维数组， c1[i][j] 表示 c1[结果][组成该结果的个数] ，然后多了一层遍历个数的循环。

// 母函数求解#include <bits/stdc++.h>using namespace std;const int MAX = 252;int ans[MAX] = {};int c1[MAX][MAX], c2[MAX][MAX];// c1[系数][累加的个数]void getAns(){ans[0] = 1;const int t[] = {0, 1, 5, 10, 25, 50};for(int n=1; n<MAX; ++n){memset(c2, 0, sizeof(c2));memset(c1, 0, sizeof(c1));for(int i=0; i<=n; ++i){c1[i][i] = 1;// 初始化}for(int i=2; i<=5; ++i){for(int j=0; j<=n; ++j){for(int c=0; c<MAX; ++c) // 遍历系数为 j, 但是个数不同的情况{if (c1[j][c]==0)continue;for(int k=0; k+j<=n; k+=t[i]){c2[k+j][c+k/t[i]] += c1[j][c];}}}memcpy(c1, c2, sizeof(c2));memset(c2, 0, sizeof(c2));}for(int i=1; i<=100; ++i) // 只取不超过100的结果{ans[n] += c1[n][i];}}}int main(void){//freopen("in.txt", "r", stdin);getAns(); // 初始化，打表int n = 0;while(cin>>n){printf("%d\n", ans[n]);}return 0;}

，纵然伤心，也不要愁眉不展，因为你不知是谁会爱上你的笑容

相关文章：

你感兴趣的文章：

标签云：