题解：P10955 正整数拆分

_Punainen_ · 2024-08-25 23:02:58 · 题解

思路

看到数字可以重复时，便容易想到使用完全背包。我们可以使 f_i 表示当某个数为 i 时总共的拆分方案的总数。则易得转移方程 f_j = f_j + f_{j-i}，即数字 j 原本的总数加上数字 j 拆分掉 i 时的总数。此时注意到，f_0 的值必为 1，因为 f_0 代表一个数被拆分完的状态，即为一种答案。另外，记得输出之前将 f_n 减去 1，因为不能将原数拆为原数加上 0。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[114514],w[114514],c[114514];
signed main(){
    int n;
    cin>>n;
    f[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            f[j]=f[j]+f[j-i];
            f[j]%=2147483648;
        }
    }
    f[n]--;
    cout<<f[n]%2147483648;
    return 0;
}