★ 输入文件:dataa.in
输出文件:dataa.out
简单对比
时间限制:1 s 内存限制:128 MB【问题描述】
现有 n 个学生, 要分成X1 ,X2 ,...,Xm ,共 m 组(m<=n, X1 ,X2 ,...,Xm 分别表示每组的学生人数),要求对于所有的i < j,Xi <= Xj ,共有多少种分组方案,求出分组方案。
【输入格式】
输入文件:dataa.in
只有一行:两个整数n,m(1<=n<=20 1<m<=10)
【输出格式】
输出文件:dataa.out
输出若干行,第一行是一个整数,表示分组方案数量.下面每行为一种分组方案,按字典序分组输出,每行的数与数之间用一个空格隔开。
【输入样例】
输入文件名: dataa.in
6 3
输出文件名: dataa.out
3
1 1 4
1 2 3
2 2 2
思路:爆搜可过。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int m,n,sum,ans; int a[10000]; int anss[1000][1000] ; void dfs(int sub){ if(sub==n+1&&sum==m){ ans++; for(int i=1;i<=n;i++) anss[ans][i]=a[i]; return ; } if(sub==n+1&&sum!=m) return; for(int i=a[sub-1];i<=m;i++){ sum=sum+i; a[sub++]=i; dfs(sub); sub--; sum=sum-i; } } int main(){ freopen("dataa.in","r",stdin); freopen("dataa.out","w",stdout); scanf("%d%d",&m,&n); a[0]=1; dfs(1); cout<<ans<<endl; for(int i=1;i<=ans;i++){ for(int j=1;j<=n;j++) cout<<anss[i][j]<<" "; cout<<endl; } return 0; }