将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。 正整数n 的这种表示称为正整数n 的划分。
输入 标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。 (0 < N <= 50, 0 < K <= N) 输出 对于每组测试数据，输出以下三行数据: 第一行: N划分成K个正整数之和的划分数目 第二行: N划分成若干个不同正整数之和的划分数目 第三行: N划分成若干个奇正整数之和的划分数目 样例输入 5 2 样例输出 2 3 3 提示 第一行: 4+1, 3+2, 第二行: 5，4+1，3+2 第三行: 5，1+1+3， 1+1+1+1+1+1 题解 1. f（i,j）表示数字i划分成j部分有几种方案数 f（i,j）=f（i-1,j-1） 这是划分出来的j部分中一定包含1 if （i-j>=j） f(i,j)+=f(i-j,j) 划分出来的j部分中都大于1 初始值 f（i,1）=f（i,i）=1 2. 初始值 f（i,1）=1; 考虑f(i,j),i需满足i>=j*(j+1)/2 (i最小等于1+2+3+......+j) 设划分的j个整数中最小的正整数是k，则从每一部分整数中抽掉1个k，k需满足k*j+j*（j-1)/2<=i 对应的方案数 f（i-j*k,j-1） j-1是因为最小数是x，减去x后值为0，因此剩余的数划分成j-1份 f（i，j）Σf（i-j*k,j-1） 3. f(i,j)表示数i划分成j个正奇数的方案数 初始值 对于奇数 f（i，1）=1，f（i,2）=0; 对于偶数 f（i,1）=0,f(i,2)=(i/2+1)/2; 考虑f（i，j），需满足i>=j j>2时 若最小的正奇数是1，对应的方案数是 f（i-1，j-1） 若最小的正奇数>1,从每个正整数中抽调2，对应的方案数是f（i-2*j,j) f(i,j)=f(i-1,j-1)+f(i-2*j,） #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,k,ans; int f[55][55]; void xx() { ans=0; memset(f,0,sizeof(f)); } int main() { while(scanf("%d%d",&n,&k)==2) { xx(); for(int i=0;i<=n;i++) { f[i][1]=1; f[i][i]=1; } for(int i=2;i<=n;i++) { for(int j=2;j<=k;j++) { f[i][j]=f[i-1][j-1]; if(i-j>=j) { f[i][j]+=f[i-j][j]; } } } cout<<f[n][k]<<endl; xx(); for(int i=1;i<=n;i++) { f[i][1]=1; } for(int j=2;j*(j+1)/2<=n;j++) { for (int i=j*(j+1)/2;i<=n;i++) { for(int k=1;k*j+j*(j-1)/2<=i;k++) { f[i][j]+=f[i-k*j][j-1]; } } } for(int j=1;j*(j+1)/2<=n;j++) { ans+=f[n][j]; } cout<<ans<<endl; xx(); for(int i=1;i<=n;i++) { if(i%2) { f[i][1]=1; f[i][2]=0; } else { f[i][1]=0; f[i][2]=(i/2+1)/2; } } for(int i=3;i<=n;i++) { for(int j=1;j<=i;j++) { f[i][j]=f[i-1][j-1]; if(i-2*j>=j) { f[i][j]+=f[i-2*j][j]; } } } for(int i=1;i<=n;i++) { ans+=f[n][i]; } cout<<ans<<endl; } }