母函数：
自己也做不出非常好的总结。
这个不错： http://blog.csdn.net/vsooda/article/details/7975485；
主要先学一下普通母函数吧。
1、
有1克、2克、3克、4克的砝码各一 枚，能称出哪几种重量？每种重量各有几种可能方案？
考虑用母函数来接吻这个问题：
我们假设x表示砝码，x的表示砝码的重量，这样：
1个1克的砝码可以用函数1+x表示，
1个2克的砝码可以用函数1+x2表示，
1个3克的砝码可以用函数1+x3表示，
1个4克的砝码可以用函数1+x4表示，
上面这四个式子懂吗？
我们拿1+x2来说，前面已经说过，x表示砝码，x的指数表示重量，即这里就是一个质量为2的砝码，那么前面的1表示什么？1代表重量为2的砝码数量为0个。（理解！）
b*x^n 就为重n的物品有几种组成方式。
2、
还有一个无限多物品的，
；
模板：
//代码很简洁， 但不太好理解；#includeusing namespace std;const int Maxn = 10001;int c1[Maxn], c2[Maxn];int main(){ int nNum; int i, j, k; while(cin >> nNum) { for(int i = 0; i <= nNum; i++) // 1 //初始化本身+1；\*3=3*/; 3=1+1+1； 3=1+2； { c1[i] = 1; c2[i] = 0; } for(int i = 2; i <= nNum; i++) // 2 我认为可以理解为把第几个多项式乘进去； { for(int j = 0; j <= nNum; j++) // 3 //遍历前边几个多项式乘积和指数； for(int k = 0; k+j <= nNum; k+=i) // 4 待乘多项式中的项指数 { c2[j+k] += c1[j]; } for(j = 0; j <= nNum; j++) // 5 、更新， c2清零； { c1[j] = c2[j]; c2[j] = 0; } } cout << c1[nNum] << endl; } return 0;}
1、
hdoj 1028--Ignatius and the Princess III
模板直接过；
2、
hdoj 1398--Square Coins
所给元素不是连续的 而是i^2 (i = 1---->n) && i^2<=289; 需要改一下模板， 2、4中的i改为i*i；
#includeint c1[301], c2[301];int main(){ int nNum; while(scanf("%d", &nNum) != EOF, nNum) { for(int i = 0; i <= nNum; i++) { c1[i] = 1; c2[i] = 0; } for(int i = 2; i*i <= nNum; i++) { for(int j = 0; j <= nNum; j++) for(int k = 0; k+j <= nNum; k+=i*i) { c2[k+j]+=c1[j]; } for(int j = 0; j <= nNum; j++) { c1[j] = c2[j]; c2[j] = 0; } } printf("%d\n", c1[nNum]); } return 0;}
3、
hdoj 1085--Holding Bin-Laden Captive!
磨人的本拉登。
题解： http://www.wutianqi.com/?p=592
#includeint c1[8001], c2[8001];int num[4];int main(){ int nNum; while(scanf("%d%d%d", &num[1], &num[2], &num[3]), num[1], num[2], num[3]) { int Max=num[1]+num[2]*2+num[3]*5; for(int i = 0; i <= Max; i++) { c1[i] = 0; c2[i] = 0; } for(int i = 0; i <= num[1]; i++) c1[i] = 1; for(int i = 0; i <= num[1]; i++) for(int j = 0; j <= num[2]*2; j+=2) c2[j+i] += c1[i]; for(int i = 0; i <= num[2]*2+num[1]*1; ++i) { c1[i] = c2[i]; c2[i] = 0; } for(int i = 0; i <= num[1]*1+num[2]*2; i++) for(int j = 0; j <= num[3]*5; j+=5) c2[j+i] += c1[i]; for(int i = 0; i <= num[2]*2+num[3]*5+num[1]*1; i++) { c1[i] = c2[i]; c2[i] = 0; } int i; for(i = 0; i <= Max; i++) if(c1[i] == 0) { printf("%d\n", i); break; } if(i==Max+1) printf("%d\n", i); } return 0;}
4、
hdoj1171--Big Event in HDU
n种物品 有n种不同价值和数目， 分成最接近的两份；
#include#include #include using namespace std;int c1[250001], c2[250001];int value[55];int amount[55];int main(){ int nNum; while(scanf("%d", &nNum) && nNum > 0) { memset(value, 0, sizeof(value)); memset(amount, 0, sizeof(amount)); int sum = 0; for(int i = 1; i <= nNum; ++i) { scanf("%d %d", &value[i], &amount[i]); sum += value[i]*amount[i]; } memset(c1, 0, sizeof(c1)); // == memset(c1, 0, sum*sizeof(c1[0])); memset(c2, 0, sizeof(c2)); for(int i = 0; i <= value[1]*amount[1]; i+=value[1]) c1[i] = 1; int len = value[1]*amount[1]; for(int i = 2; i <= nNum; ++i) { for(int j = 0; j <= len; ++j) for(int k = 0; k <= value[i]*amount[i]; k+=value[i]) { c2[k+j] += c1[j]; } len += value[i]*amount[i]; for(int j = 0; j <= len; ++j) { c1[j] = c2[j]; c2[j] = 0; } } for(int i = sum/2; i >= 0; --i) { if(c1[i]) { printf("%d %d\n", sum-i, i); break; } } } return 0;}