首页 > 代码库 > codevs 1039 数的划分 x
codevs 1039 数的划分 x
1039 数的划分
2001年NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种划分方案被认为是相同的。
1 1 5
1 5 1
5 1 1
问有多少种不同的分法。
输入描述 Input Description
输入：n，k (6<n<=200，2<=k<=6)
输出描述 Output Description
输出：一个整数，即不同的分法。
样例输入 Sample Input
7 3
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
{四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}
分类标签 Tags 点此展开
划分型DP 动态规划 大陆地区 NOIP全国联赛提高组 2001年
-------------------------------------------代码~------------------------------------------------
1 #include<iostream> 2 #include<cstdio> 3 4 using namespace std; 5 6 int g=0,n,k; 7 8 void sou(int x,int y,int z) 9 {10 if(y==1&&x<z) return ;11 if(y==1&&x>=z) {12 g++;13 return ;14 }15 int i;16 for(i=z; i<=x; i++) {17 //if(i-z>=z)18 sou(x-i,y-1,i);19 }20 }21 int main()22 {23 cin>>n>>k;24 sou(n,k,1);25 cout<<g;26 return 0;27 }
codevs 1039 数的划分 x
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。