- 描述
-
将正整数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
查看
提取递归边界的方法就是看递归函数中的参数是如何变化的，边界的作用就是防止无穷递归
#include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<string> #include<map> #include<cstring> #define DEBUG(x) cout << #x << " = " << x << endl using namespace std; const int MAXN=55; int N,K; ///前i个数中k个数和为j的种数 int dp1[MAXN][MAXN][MAXN]; int Num1(int i,int j,int k) { if(dp1[i][j][k]!=-1)return dp1[i][j][k]; if(j==0&&k==0)return 1; if(k==0)return 0; if(i==0)return 0; if(j==0)return 0; int r=Num1(i-1,j,k); if(j>=i)r+=Num1(i,j-i,k-1); dp1[i][j][k]=r; return r; } ///前i个数和为j的种数 int dp2[MAXN][MAXN]; int Num2(int i,int j) { if(j==0)return 1; if(i==0)return 0; if(dp2[i][j]!=-1)return dp2[i][j]; int r=Num2(i-1,j); if(j>=i)r+=Num2(i-1,j-i); dp2[i][j]=r; return r; } ///前i个数中的正奇数和为j的种数 int dp3[MAXN][MAXN]; int Num3(int i,int j) { if(j==0)return 1; if(i==0)return 0; if(dp3[i][j]!=-1)return dp3[i][j]; int r=Num3(i-1,j); if(i%2&&i<=j)r+=Num3(i,j-i); dp3[i][j]=r; return r; } int main() { // freopen("in.txt","r",stdin); while(scanf("%d %d",&N,&K)!=EOF) { memset(dp1,0xff,sizeof(dp1)); memset(dp2,0xff,sizeof(dp2)); memset(dp3,0xff,sizeof(dp3)); printf("%d ",Num1(N,N,K)); printf("%d ",Num2(N,N)); printf("%d ",Num3(N,N)); } return 0; }