算法 | 时间 |
---|---|
DFS + 剪枝 | 36ms |
递归子问题 | 46ms |
最优 DP | 6ms |
记忆化搜索 | 5ms |
朴素完全背包 | 20ms |
状态优化的完全背包 | 8ms |
DFS
版本 | 时间 |
---|---|
直接暴搜 | TLE |
缩小下界 | 850ms |
缩小上界 | 44ms |
除法变乘 | 36ms |
将数字 $n$ 分成 $k$ 份,即求 $x_1 + x_2 + … + x_k = n$ 的解,和 842. 排列数字 类似,可以逐一枚举 $x_i$,不做任何优化,每个位置枚举 $1 \sim n$。但题中说明 $1, 1, 5$,$1, 5, 1$ 和 $5, 1, 1$ 算同一组解,即求解的是组合数,而非排列数。可将路径保存到 set
,再把可行解保存到 unordered_set
,最后输出可行解个数,但这样显然多走了太多无用分支,复杂度是 $O(n^k)$
考虑如何剪枝,由于一组数字的排序(假设从小到大)是唯一的,因此我们可以以不递减顺序枚举,即让 $x_i >= x_{i-1}$,也就是下界是 $x_{i-1}$
再考虑缩小上界,我们枚举到 $x_i$ 时,它不能超过 $m = n - (x_1 + x_2 + … + x_{i-1})$。又由于 $x_i$ 是 $x_{i} \sim x_k$ 中最小的数,由于和是固定的,$x_i$ 不能超过它们的平均数,否则后面的数都会超过平均数,和就会超过 $m$
于是我们有了剪枝后的代码
#include <iostream>
using namespace std;
int n, k, ans;
void dfs(int u, int prev, int m) {
if (u == k) {
if (m >= prev) ans ++;
return;
}
for (int i = prev; i <= m / (k - u + 1); i ++)
dfs(u + 1, i, m - i);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k;
dfs(1, 1, n);
cout << ans << '\n';
return 0;
}
由于乘法比除法快,考虑将上界转为乘法。当枚举到 $x_i$ 时,$m = x_i + x_{i+1} + … +x_k$,$x_i$ 要取最大,则 $x_{i+1} \sim x_k$ 要尽可能小,它们最小也要等于 $x_i$,所以 $x_i <= m - (k - i) * x_i$,则有以下代码
void dfs(int u, int prev, int m) {
if (u == k) {
if (m >= prev) ans ++;
return;
}
for (int i = prev; i <= m - (k - u) * i; i ++)
dfs(u + 1, i, m - i);
}
递归子问题
记 $f(n, k)$ 是把 $n$ 分解为 $k$ 个数的和的所有分法
有两种情况
- 这 $k$ 个数至少包含一个 $1$
- 这 $k$ 个数都大于 $1$
对于计数类问题,要求划分出的子问题不重不漏,上述分法满足条件
这种划分标准在基础课讲过,见 900. 整数划分
-
对于情况 $1$,我们可以找到一个 $1$,把它去掉,则问题等价于把 $n - 1$ 分解为 $k - 1$ 个数和,即 $f(n - 1, k - 1)$
-
对于情况 $2$,我们可以把 $k$ 个数每个都减去 $1$,则问题等价于把 $n - k$ 分解为 $k$ 个数的和,即 $f(n - k, k)$
原问题的解等于两个子问题解的和,即 $f(n, k) = f(n - 1, k - 1) + f(n - k, k)$
考虑递归出口
- 当 $n < k$ 时,无法划分,$f(n, k) = 0$
- 当 $n = k$ 时,只能分成 $k$ 个 $1$,$f(n, k) = 1$
- 当 $k = 1$ 时,只能分成 $1$ 个 $n$,$f(n, k) = 1$
于是有如下代码
#include <iostream>
using namespace std;
int resolve(int n, int k) {
if (n < k) return 0;
if (n == k || k == 1) return 1;
return resolve(n - 1, k - 1) + resolve(n - k, k);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k; cin >> n >> k;
cout << resolve(n, k) << '\n';
return 0;
}
最优 DP
我们用闫氏 DP 分析法过一遍流程:DP 是在有限集求最优解或合法解数,即方案数有限,但通常为指数级
状态表示,化零为整
即从逐个枚举到每次求一个集合
集合
将整数 $i$ 划分为 $j$ 个数的和的所有分法
属性
集合元素个数,$f[i, j]$ 表示将整数 $i$ 划分为 $j$ 个数的和的所有分法的数量
答案
$f[n, k]$
状态计算,化整为零
即把集合划分为若干子集,寻找原问题和子问题的递推关系,再从初始条件递推到原问题
划分
计数类 DP 要求不重不漏。每个子问题又可分为变化的部分和不变的部分
- 最小数字等于 $1$。这类划分,不变的部分是每个划分都至少含有一个 $1$,变化的部分是除去一个 $1$ 后的 $j - 1$ 个数,去掉不变的部分,问题等价于 $f[i - 1, j - 1]$
- 最小数字大于 $1$。这类划分,不变的部分是划分中的每个数都能写成 $1 + x$,变化的部分是 $x$,则每个数都去掉不变的 $1$ 后问题等价于 $f[i - j, j]$
条件
$j <= min(i, k)$
初始
$f[0, 0] = f[i, 1] = 1, i >= 1$
$f[0, i] = f[i, 0] = 0, i >= 1$
#include <iostream>
using namespace std;
const int N = 210, M = 10;
int f[N][M];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k; cin >> n >> k;
f[0][0] = 1;
for (int i = 1; i <= n; i ++) f[i][1] = 1;
for (int i = 1; i <= n; i ++)
for (int j = 2; j <= min(i, k); j ++)
f[i][j] = f[i - 1][j - 1] + f[i - j][j];
cout << f[n][k] << '\n';
return 0;
}
记忆化搜索
把上面两种方法组合,就变成记忆化搜索
#include <cstring>
#include <iostream>
using namespace std;
const int N = 210, M = 10;
int f[N][M];
int dfs(int i, int j) {
if (i < j) return 0;
auto& fij = f[i][j];
if (~fij) return fij;
return fij = dfs(i - 1, j - 1) + dfs(i - j, j);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k; cin >> n >> k;
memset(f, -1, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= n; i ++) f[i][1] = 1;
cout << dfs(n, k) << '\n';
return 0;
}
完全背包
问题可转化为以下完全背包问题:
有 $n$ 种物品和一个容量是 $n$ 的背包,每种物品有无限件可用,第 $i$ 种物品的体积是 $i$。求解用 $m$ 件物品装满背包的所有方法
再用闫氏 DP 分析法过一遍流程:DP 是在有限集求最优解或合法解数,即方案数有限,但通常为指数级
状态表示,化零为整
即从逐个枚举到每次求一个集合
集合
只从前 $i$ 种物品选 $k$ 件,且体积等于 $j$ 的所有选法
属性
集合元素个数,$f[i, j, k]$ 表示只从前 $i$ 种物品选 $k$ 件,且体积等于 $j$ 的所有选法的个数
答案
$f[n, n, m]$
状态计算,化整为零
即把集合划分为若干子集,寻找原问题和子问题的递推关系,再从初始条件递推到原问题
划分
计数类 DP 要求不重不漏。每个子问题又可分为变化的部分和不变的部分。通常把最后一次不同作为划分标准,此处为选几件第 $i$ 种物品
前 $i$ 种要选 $k$ 件,则第 $i$ 种可以选 $l$ 件,这些选法不变的部分是选了 $l$ 件物品 $i$,变化的部分是要从前 $i - 1$ 种物品选 $k - l$ 件,使体积等于 $j - l * i$
则 $f[i, j, k] = \sum_{l=0}^{k} f[i - 1][j - l * i][k - l]$
条件
$0 <= k <= min(n, m), 0 <= l <= k, l \times i <= j$
初始
$f[0][0][0] = 1$
则有如下朴素写法
#include <iostream>
using namespace std;
const int N = 210, M = 10;
int f[N][N][M];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m; cin >> n >> m;
f[0][0][0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= n; j ++)
for (int k = 0; k <= min(n, m); k ++)
for (int l = 0; l <= k && j >= l * i; l ++)
f[i][j][k] += f[i - 1][j - l * i][k - l];
cout << f[n][n][m] << '\n';
return 0;
}
状态优化
> f[i][j][k] = f[i-1][j][k] + f[i-1][j-i][k-1] + f[i-1][j-2i][k-2] + f[i-1][j-3i][k-3] + ...
> f[i][j-i][k-1] = f[i-1][j-i][k-1] + f[i-1][j-2i][k-2] + f[i-1][j-3i][k-3] + ...
> f[i][j][k] = f[i-1][j][k] + f[i][j-i][k-1]
于是有
#include <iostream>
using namespace std;
const int N = 210, M = 10;
int f[N][N][M];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m; cin >> n >> m;
f[0][0][0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= n; j ++)
for (int k = 0; k <= min(n, m); k ++) {
f[i][j][k] = f[i - 1][j][k];
if (j >= i && k >= 1)
f[i][j][k] += f[i][j - i][k - 1];
}
cout << f[n][n][m] << '\n';
return 0;
}
空间优化
$f[i]$ 只依赖 $f[i]$ 和 $f[i - 1]$,可去掉第一维,同时判断也能合并到循环里
#include <iostream>
using namespace std;
const int N = 210, M = 10;
int f[N][M];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m; cin >> n >> m;
f[0][0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = i; j <= n; j ++)
for (int k = 1; k <= m; k ++)
f[j][k] += f[j - i][k - 1];
cout << f[n][m] << '\n';
return 0;
}
请问,DP解法,为什么还需要小于k呢
nb
大哥哥,你好帅啊qwq
tql
好优秀的题解,%%%
很棒很不错啊