题面的意思竟然是必须分出 $N$ 个分身,乌鱼了。
类似背包优化方式的动态规划
设 $f[i][j][s]$ 表示考虑从 $[0, \ i]$ 选数,共选 $j$ 个,和为 $s$ 的方案数。
这样就能保证是无序的。考虑其转移:
-
不选 $i$:$f[i][j][s] = f[i - 1][j][s]$
-
选 $i$:$f[i][j][s] = f[i - 1][j - 1][s - i] + f[i - 1][j - 2][s - 2i] + \cdots + f[i - 1][j - k][s - ki]$
- 考虑 $f[i][j - 1][s - i] = f[i - 1][j - 1][s - i] + f[i - 1][j - 2][s - 2i] + \cdots + f[i - 1][j - k][s - ki]$
综合得到 $f[i][j][s] = f[i - 1][j][s] + f[i][j - 1][s - i]$,可以用滚动数组优化第一维。
边界条件:$f[0][i][0] = 1, \ 0 \leqslant i \leqslant N$。
最终答案:$f[M][N][M]$。
时间复杂度 $O(\sum\limits_{i = 1}^{t}{N_iM_i^2})$
C++ 代码
#include <bits/stdc++.h>
using LL = long long;
void solve() {
int M, N;
std::cin >> M >> N;
std::vector f(N + 1, std::vector<int>(M + 1));
for (int i = 0; i <= N; i += 1) {
f[i][0] = 1;
}
for (int i = 1; i <= M; i += 1) {
auto g = f;
for (int j = 1; j <= N; j += 1) {
for (int s = i; s <= M; s += 1) {
g[j][s] += g[j - 1][s - i];
}
}
f.swap(g);
}
std::cout << f[N][M] << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
时间复杂度更低的 dp
,类似篮球杯的一道题
设 $f[i][j]$ 表示选了 $i$ 个数,总和为 $j$ 的方案数。
-
有 $0$:$f[i][j] = f[i - 1][j]$,表示去掉一个 $0$
-
没有 $0$:说明最小是 $1$,那就让每个数都减去 $1$,恰好对应 $f[i][j - i]$ 的方案。
因此 $f[i][j] = f[i - 1][j] + f[i][j - i]$,同样可以滚动数组优化。
边界条件:$f[0][0] = 1$。
答案:$f[N][M]$。
时间复杂度 $O(\sum\limits_{i = 1}^t{N_iM_i})$
c++ 代码
#include <bits/stdc++.h>
using LL = long long;
void solve() {
int M, N;
std::cin >> M >> N;
std::vector<int> f(M + 1);
f[0] = 1;
for (int i = 1; i <= N; i += 1) {
auto g = f;
for (int j = i; j <= M; j += 1) {
g[j] += g[j - i];
}
f.swap(g);
}
std::cout << f[M] << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}