首页 > 代码库 > 整数划分母函数

整数划分母函数

http://acm.nyist.net/JudgeOnline/problem.php?pid=90

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int c[10000];int c1[10000];int main(){    int n;    int val[100], sum[100];    while (cin >> n){        for (int i = 0; i < n; i++)            val[i] = i + 1, sum[i] = n / (i + 1);        memset(c, 0, sizeof(c));        c[0] = 1;        for (int i = 0; i < n; i++){            for (int j = 0; j <= sum[i]; j++){                for (int k = 0; k + j*val[i] <= n; k++)                    c1[k + j*val[i]] += c[k];            }            for (int j = 0; j <= n; j++)                c[j] = c1[j], c1[j] = 0;        }        printf("%d\n", c[n]);    }    return 0;}

 

整数划分母函数