題目連結
非常好的題目！先想三維再想二維！
核心的想法是，如果能延伸，我們就延伸！延伸長度的話呢？枚舉他！
AC Code (3D Recursive DP)
$dp(n, k, m)$是不是只跟$dp(n - i, k - 1, min(m, n - i))$有關係呢？
核心精神是：我們嘗試去對於$dp(…, k - 1, …)$做延伸，至於延伸長度呢？就是 $n - i$!
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
ll dp[55][55][55];
ll cal(int n, int k, int m)
{
if (n == 0 || k == 0 || m == 0)
return 0;
if (k > n || m > n)
return 0;
if (k == 1) {
if (n == m)
return 1;
return 0;
}
if (dp[n][k][m] != -1)
return dp[n][k][m];
ll ret = 0;
for (int i = 1; i <= m; i++) {
// add one group of bar with length i to the end of the set (n - i, k - 1,
// ...) so just make sure that i is not longer than m also, change the m
// when recursing
ret += cal(n - i, k - 1, min(m, n - i));
}
return dp[n][k][m] = ret;
}
int main()
{
int n, k, m;
while (scanf("%d %d %d", &n, &k, &m) == 3) {
memset(dp, -1, sizeof(dp));
dp[1][1][1] = 1;
printf("%lld\n", cal(n, k, m));
}
return 0;
}
|
AC Code (2D DP)
上面的那種做法你會發現 $m$ 參數其實有點多餘！
那就拿掉吧！
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
int main()
{
int n, k, m;
while (scanf("%d %d %d", &n, &k, &m) == 3) {
ll dp[55][55];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
// dp[i][j] = ans for i groups, j bars, and at most m bars per groups
// start with 1 group, 1...n bars
// 2 groups, for every bar count j, try to extent it with 1 group (j - (1 ~ m))
for (int i = 1; i <= k; i++) { // groups
for (int j = 1; j <= n; j++) { // bars
for (int x = 1; x <= m; x++) { // at most x bars
if (j - x >= 0)
dp[i][j] += dp[i - 1][j - x];
}
}
}
printf("%lld\n", dp[k][n]); // (k, n, m), m is fixed for this dp table
}
return 0;
}
|