题目大意
题目链接
每组输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)
对于输入的 n,k;
第一行： 将n划分成若干正整数之和的划分数。
第二行： 将n划分成k个正整数之和的划分数。
第三行： 将n划分成最大数不超过k的划分数。
第四行： 将n划分成若干个 奇正整数之和的划分数。
第五行： 将n划分成若干不同整数之和的划分数。
第六行： 打印一个空行
题解
妥妥的动规， 说一下每一个的转移方程
注意 我们编号 a[0] = 1, …a[n - 1] = n… a[i - 1] = i。 因为组成n的正整数不可能超过n
1
2
| f[i][j] 表示的是用前i个数字， 组成数字j的方案数
f[i][j] += f[i - 1][j - s * i]; 0 <= s <= j / i; j - s * i 中的i 是a[i - 1]
|
1
2
| f[i][j][s] 表示的是 用前i个数字 用了j次 组成数字s 的方案数
f2[i][j][s] += f2[i - 1][j - t][s - t * i]; t <= j && t * i <= s
|
1
2
3
| f[i][j]表示的是用前i个数字， 组成数字j的方案数
f[i][j] += f[i - 1][j - s * i]; 0 <= s <= j / i; j - s * i 中的i 是a[i - 1]
|
1
2
3
4
| f[i][j]表示的是用前i个数字， 组成数字j的方案数
f[i][j] = f[i - 1][j]; i为偶数
f[i][j] += f[i - 1][j - s * i]; 0 <= s <= j / i; j - s * i 中的i 是a[i - 1] i为奇数
|
1
| 千千万万别忘了输出空行， 我因为这个收获了一发pe
|
AC代码
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| #include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define debug cout << "fuck!\n";
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> P;
int f1[100][100], f2[100][100][100], f3[100][100], f4[100][100], f5[100] ;
int main() {
int n, k;
while(cin >> n >> k){
memset(f1, 0, sizeof f1);
f1[0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = 0; j <= n; j++){
for (int s = 0; s <= j / i; s++){
f1[i][j] += f1[i - 1][j - s * i];
}
}
}
cout << f1[n][n] << "\n";
memset(f2, 0, sizeof f2);
f2[0][0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = 0; j <= k; j++){
for (int s = 0; s <= n; s++){
for (int t = 0; t <= j && t * i <= s; t++){
f2[i][j][s] += f2[i - 1][j - t][s - t * i];
}
}
}
}
cout << f2[n][k][n] << "\n";
memset(f3, 0, sizeof f3);
f3[0][0] = 1;
for (int i = 1; i <= k; i++){
for (int j = 0; j <= n; j++){
for (int s = 0; s <= j / i; s++){
f3[i][j] += f3[i - 1][j - s * i];
}
}
}
cout << f3[k][n] << "\n";
memset(f4, 0, sizeof f4);
f4[0][0] = 1;
for (int i = 1; i <= n; i ++){
for (int j = 0; j <= n; j++){
if (i % 2 == 0){
f4[i][j] = f4[i - 1][j];
continue;
}
for (int s = 0; s <= j / i; s++){
f4[i][j] += f4[i - 1][j - s * i];
}
}
}
if (n % 2 == 1)
cout << f4[n][n] << "\n";
else
cout << f4[n - 1][n] << "\n";
memset(f5, 0, sizeof f5);
f5[0] = 1;
for (int i = 1; i <= n; i++){
for (int j = n; j >= i; j--){
f5[j] += f5[j - i];
}
}
cout << f5[n] <<"\n";
cout << "\n";
}
return 0;
}
|
1
| 恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。
|