首页 > 代码库 > codevs——1039 数的划分
codevs——1039 数的划分
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;}
dp
思路:
我们可以推出，每一个状态可以由这两种情况转化而来
一是：前面的i-1个数用了k-1次划分，那么最后这个数和前面的分开一共就是k次划分。
二是：最后的几个数在一块分，那么前面就一共用了j次划分。
至于为什么是dp【0】【0】=1，在0个数0次划分时一共有1种划分方法。
代码：
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 300using namespace std;int read(){ int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f;}int n,k,ans,dp[N][N];int main(){ n=read(),k=read(); dp[0][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=min(i,k);j++) dp[i][j]=dp[i-j][j]+dp[i-1][j-1]; ans=dp[n][k]; printf("%d",dp[n][k]); return 0;}
搜索
代码：
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#define N 300using namespace std;int n,m,ans,b[N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f;}int dfs(int k,int end,int begin){ if(k==m) { if(end>=begin) ans++; return 0; } for(int i=begin;i<end;i++) { b[k]=i; dfs(k+1,end-i,i); } }int main(){ n=read();m=read(); dfs(1,n,1); printf("%d",ans); return 0;}
codevs——1039 数的划分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。