复杂的整数划分问题
- 总时间限制:
- 200ms
- 内存限制:
- 65536kB
- 描述
- 将正整数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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | #include<cstdio> #include<cstring> using namespace std; int arr_1[51][51][51]; int arr_2[51][51]; int arr_3[51][51]; int N_To_K(int n,int max,int k){ int r=arr_1[n][max][k]; if(r!=-1)return r; else{ if(max==0){ r=0; }else{ if(k==0){ if(n==0)r=1; else r=0; }else{ if(n>=max)r=N_To_K(n-max,max,k-1)+N_To_K(n,max-1,k); else r=N_To_K(n,n,k); } } } arr_1[n][max][k]=r; return r; } int N_To_Diff(int n,int max){ int r=arr_2[n][max]; if(r!=-1)return r; else{ if(max==0||n<0)r=0; else if(n==0||n==1)r=1; else{ if(n>=max){ r=N_To_Diff(n-max,max-1)+N_To_Diff(n,max-1); } else r=N_To_Diff(n,n); } } arr_2[n][max]=r; return r; } int N_To_Odd(int n,int max){ int r=arr_3[n][max]; if(r!=-1)return r; else{ if(max<=0||n<0)r=0; else if(n==0||n==1)r=1; else{ if(n>=max){ if(max%2==0)r=N_To_Odd(n,max-1); else r=N_To_Odd(n-max,max)+N_To_Odd(n,max-2); } else r=N_To_Odd(n,n); } } arr_3[n][max]=r; return r; } int main(){ memset(arr_1,-1,sizeof(arr_1)); memset(arr_2,-1,sizeof(arr_2)); memset(arr_3,-1,sizeof(arr_3)); int n,k; while(~scanf("%d %d",&n,&k)){ printf("%d\n%d\n%d\n",N_To_K(n,n,k),N_To_Diff(n,n),N_To_Odd(n,n)); } } |