技术教程 编程教程 51nod1201 整数划分 正文

51nod1201 整数划分

2023-05-23,,

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 整数划分的相关教程结束。

《51nod1201 整数划分.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!