首页 > 代码库 > 51nod1201_dp思维题
51nod1201_dp思维题
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1201
将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。
分析：这题关键在于不同的整数
一个包含数字最多的划分必定是1+2+3+....+m == n
这样(m + 1) * m <= 2 * n
可以确定m是O(sqrt(n))级别的
想到这里很容易想到用dp[i][j]表示I这个数分成j的数组成的划分有多少种。
方程为：dp[i][j] = dp[i - j][j] + dp[i - j][j - 1]
前者表示将i - j划分为j个数，每个数加1就是i划分为j个数的方案了。
但是前者这样有i-j的方案+1形成i分为j个数的方案是不完全的，因为没有1
后者则补充了这部分的答案，表示i-j划分为j个数，每个数+1，并且方案再加入一个1这个元素。
由于数不重复，所以1的个数只能为1个。
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <cmath> 9 #include <queue>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 const int mod = 1e9 + 7;16 int dp[50010][350];17 int main()18 {19 int n;20 scanf("%d", &n);21 int m = sqrt(2 * n);22 memset(dp, 0, sizeof(dp));23 dp[0][0] = 1;24 for(int j = 1; j <= m; j++)25 {26 for(int i = j; i <= n; i++)27 {28 dp[i][j] = (dp[i-j][j] + dp[i-j][j-1]) % mod;29 //cout << i <<" "<<j << " "<<dp[i][j]<<endl;30 }31 }32 int res = 0;33 for(int i = 1; i <= m; i++)34 res = (res + dp[n][i]) % mod;35 printf("%d\n", res);36 return 0;37 }
51nod1201_dp思维题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。