vjudge链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18473

题意:对于给定的正整数n,将这个数分成不超过n个数的和,问能找到几个这样的划分。

可以转化为划分数问题,用动规的思想解决,dp[n][n]即为最终结果。也可以用母函数来解决。

#include <cstdio>
using namespace std;

int n, dp[128][128];
int main(){
    dp[0][0] = 1;
    for(int i = 1; i <= 120; ++i)
        for(int j = 0; j <= 120; ++j){
            if(j >= i) dp[i][j] = dp[i-1][j] + dp[i][j-i];
            else dp[i][j] = dp[i-1][j];
        }
    while(~scanf("%d", &n)) printf("%d\n", dp[n][n]);
    return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 128;
int n, s[maxn], t[maxn];
int main(){
    ios::sync_with_stdio(false);
    while(cin >> n){
        for(int i = 0; i <= n; ++i)
            s[i] = 1, t[i] = 0;
        for(int i = 2; i <= n; ++i){
            for(int j = 0; j <= n; ++j)
                for(int k = 0; j + k <= n; k += i)
                    t[j+k] += s[j];
            for(int j = 0; j <= n; ++j)
                s[j] = t[j], t[j] = 0;
        }
        cout << s[n] << endl;
    }
    return 0;
}

 

欢迎留言