给定一个自然数 N,要求把 N 拆分成若干个正整数相加的形式,参与加法运算的数可以重复。

注意:

  • 拆分方案不考虑顺序。
  • 至少拆分成 2 个数的和。
  • 求拆分的方案数 mod 2147483648 的结果。

输入格式:

一个自然数 N

输出格式:

输入一个整数,表示结果。

数据范围:

1 ≤ N ≤ 4000

示例输入:

7

示例输出:

14

代码实现

#include <iostream>
using namespace std;
const int N = 4010, MOD = 2147483648;

int n, dp[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    dp[0] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = i; j <= n; ++j)
            dp[j] = (dp[j] + dp[j - i] * 1ll)
    }
    cout << dp[n];
    return 0;
} 
分类: DP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status