首页 > 代码库 > 51nod1201 整数划分
51nod1201 整数划分
01背包显然超时。然后就是一道神dp了。dp[i][j]表示j个数组成i的方案数。O(nsqrt(n))
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)const int nmax=5e4+5;const int mod=1e9+7;int dp[nmax][355];int main(){ int n;scanf("%d",&n); dp[1][1]=1; rep(i,2,n) rep(j,1,min(i,350)) dp[i][j]=(dp[i-j][j]+dp[i-j][j-1])%mod; int ans=0; rep(i,1,350) ans=(ans+dp[n][i])%mod; printf("%d\n",ans); return 0;}
1201 整数划分
基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题
收藏
关注
将N分为若干个不同整数的和,有多少种不同的划分方式,例如:n = 6,{6} {1,5} {2,4} {1,2,3},共4种。由于数据较大,输出Mod 10^9 + 7的结果即可。
Input
输入1个数N(1 <= N <= 50000)。
Output
输出划分的数量Mod 10^9 + 7。
Input示例
6
Output示例
4
51nod1201 整数划分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。