描述
将正整数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
分析
整数划分问题这几个变形确实很经典，需要一个个说明下： 设dp[n][m]表示数n划分方案中，每个数 不大于m 的划分数。
N划分成若干个可相同正整数之和
划分分两种情况：
划分中每个数都小于m：则划分数为dp[n][m-1]。划分中至少有一个数等于m：则从n中减去去m，然后从n-m中再划分，则划分数为dp[n-m][m]。
动态转移方程：dp[n][m]=dp[n][m-1]+dp[n-m][m]。
N划分成若干个不同正整数之和
划分分两种情况：
划分中每个数都小于m：则划分数为dp[n][m-1]。划分中至少有一个数等于m：则从n中减去m，然后从n-m中再划分，且再划分的数中每个数要小于m, 则划分数为dp[n-m][m-1]。
动态转移方程：dp[n][m]=dp[n][m-1]+dp[n-m][m-1]。
N划分成K个正整数之和
设dp[n][k]表示数n划分成k个正整数之和时的划分数。 划分分两种情况：
划分中不包含1：则要求每个数都大于1，可以先拿出k个1分到每一份，之后在n-k中再划分k份，即dp[n-k][k]。划分中包含1：则从n中减去1，然后从n-1中再划分k-1份, 则划分数为dp[n-1][k-1]。
动态转移方程：dp[n][k]=dp[n-k][k]+dp[n-1][k-1]。
N划分成若干个奇正整数之和
设f[i][j]表示将数i分成j个正奇数，g[i][j]表示将数i分成j个正偶数。 首先如果先给j个划分每个分个1，因为奇数加1即为偶数，所以可得： f[i-j][j] = g[i][j]。 划分分两种情况：
划分中不包含1：则要求每个数都大于1，可以先拿出k个1分到每一份，刚可将问题转换为"从i-j中划分j个偶数"，即g[i-j][j]。划分中包含1：则从n中减去1，然后从n-1中再划分k-1份, 则划分数为dp[n-1][k-1]。
动态转移方程：f[i][j]=f[i-1][j-1]+g[i-j][j]。
实现
#include <iostream>
#include <cstring>
using namespace std
;
#define N 51
int dp1
[N
][N
];
int dp2
[N
][N
];
int dp3
[N
][N
];
int f
[N
][N
];
int g
[N
][N
];
void initDivideInt() {
memset(dp1
, 0, sizeof(dp1
));
memset(dp2
, 0, sizeof(dp2
));
memset(dp3
, 0, sizeof(dp3
));
for (int i
= 1; i
< N
; i
++) {
for (int j
= 1; j
< N
; j
++) {
if (i
< j
) {
dp1
[i
][j
] = 0;
dp2
[i
][j
] = dp2
[i
][i
];
dp3
[i
][j
] = dp3
[i
][i
];
}
else if (i
== j
) {
dp1
[i
][j
] = 1;
dp2
[i
][j
] = dp2
[i
][j
- 1] + 1;
dp3
[i
][j
] = dp3
[i
][j
- 1] + 1;
}
else {
dp1
[i
][j
] = dp1
[i
- j
][j
] + dp1
[i
- 1][j
- 1];
dp2
[i
][j
] = dp2
[i
][j
- 1] + dp2
[i
- j
][j
- 1];
dp3
[i
][j
] = dp3
[i
][j
- 1] + dp3
[i
- j
][j
];
}
}
}
}
void initDivideOdd() {
f
[0][0] = 1;
g
[0][0] = 1;
for (int i
= 1; i
< N
; i
++) {
for (int j
= 1; j
<= i
; j
++) {
g
[i
][j
] = f
[i
- j
][j
];
f
[i
][j
] = f
[i
- 1][j
- 1] + g
[i
- j
][j
];
}
}
}
int main() {
int n
, k
;
initDivideInt();
initDivideOdd();
while (cin
>> n
>> k
) {
cout
<< dp1
[n
][k
] << endl
;
cout
<< dp2
[n
][n
] << endl
;
int sum
= 0;
for (int i
= 0; i
<= n
; i
++) {
sum
+= f
[n
][i
];
}
cout
<< sum
<< endl
;
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-660544.html
