1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
#include <iostream> using namespace std; // Author: Tanky Woo // www.wutianqi.com const int _max = 10001; // c1是保存各项质量砝码可以组合的数目 // c2是中间量，保存没一次的情况 int c1[_max], c2[_max]; int main() { //int n,i,j,k; int nNum; // int i, j, k; while(cin >> nNum) { for(i=0; i<=nNum; ++i) // ---- ① { c1[i] = 1; c2[i] = 0; } for(i=2; i<=nNum; ++i) // ----- ② { for(j=0; j<=nNum; ++j) // ----- ③ for(k=0; k+j<=nNum; k+=i) // ---- ④ { c2[j+k] += c1[j]; } for(j=0; j<=nNum; ++j) // ---- ⑤ { c1[j] = c2[j]; c2[j] = 0; } } cout << c1[n] << endl; } return 0; }
我们来解释下上面标志的各个地方：
① 、首先对c1初始化，由第一个表达式(1+x+x2+..xn)初始化，把质量从0到n的所有砝码都初始化为1.
② 、 i从2到n遍历，这里i就是指第i个表达式，上面给出的第二种母函数关系式里，每一个括号括起来的就是一个表达式。
③、j 从0到n遍历，这里j就是只一个表达式里第j个变量，比如在第二个表达式里：(1+x2+x4….)里，第j个就是x2*j.
③ k表示的是第j个指数，所以k每次增i（因为第i个表达式的增量是i）。
④ 、把c2的值赋给c1,而把c2初始化为0，因为c2每次是从一个表达式中开始的