本文主要是介绍【CHOJ 5202】自然数拆分Lunatic版【DP】【完全背包】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
题目链接：http://contest-hunter.org:83/contest/0x50「动态规划」例题/5202 自然数拆分Lunatic版
求一个自然数能被多少个除零和自己以外的自然数相加得到。答案取模 2 31 2^{31} 231。
思路：
由于每一个自然数可以被无限次使用，所以这道题是一道完全背包的题目。
设 f [ i ] f[i] f[i]为达到 i i i的方案总和取模 2 31 2^{31} 231的值，那么就有方程 f [ i ] = ( f [ i ] + f [ i − j ] ) % M O D ( 1 ≤ j ≤ i ≤ n ) f[i]=(f[i]+f[i-j])\%MOD\ \ (1\leq j\leq i \leq n) f[i]=(f[i]+f[i−j])%MOD (1≤j≤i≤n)
代码：
#include <cstdio>
#define MOD 2147483648ll
using namespace std;int n;
long long f[4001];int main()
{scanf("%d",&n);f[0]=1;for (int j=1;j<=n;j++)for (int i=j;i<=n;i++)f[i]=(f[i]+f[i-j])%MOD;printf("%lld\n",f[n]%MOD-1);return 0;
}
这篇关于【CHOJ 5202】自然数拆分Lunatic版【DP】【完全背包】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
