【CHOJ 5202】自然数拆分Lunatic版【DP】【完全背包】

本文主要是介绍【CHOJ 5202】自然数拆分Lunatic版【DP】【完全背包】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：http://contest-hunter.org:83/contest/0x50「动态规划」例题/5202 自然数拆分Lunatic版
求一个自然数能被多少个除零和自己以外的自然数相加得到。答案取模$2^{31}$。

---

思路：

由于每一个自然数可以被无限次使用，所以这道题是一道完全背包的题目。
设$f[i]$为达到$i$的方案总和取模$2^{31}$的值，那么就有方程$$f[i]=(f[i]+f[i-j])\%MOD(1\le j\le i\le 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】【完全背包】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---