组合数学+费用背包+刷表，G2 - Playlist for Polycarp (hard version)
目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
| G2 - Playlist for Polycarp (hard version) |
二、解题报告
1、思路分析
一眼dp，但是这个dp思路和代码都不太好想
首先是涉及到组合数学的分配问题
方案数怎么求？
既涉及到了相邻的顺序，又涉及到了容量/费用
我们可以单独考虑然后相乘：
f(i, j, k, x) 为 选取 i 个类型1，j个 类型2，k 个类型3，并且以类型x结尾，且无相同相邻项的方案数
这个dp可太简单了，O(1)转移，O(N^3 * 3)的方案数，很好搞定
再考虑 g(i, j, k, t) 即 选 i 个类型1，j个 类型2，k 个类型3，总费用为t（费用指的是时间和）的方案数
这是个费用背包问题，我们直接求是O(N ^ 4 T)，太大了
考虑转换一下，g(j, k, p) 为 j个 类型2，k 个类型3 总费用为t方案数，h(i, T - p)为i个类型1，总费用为t的方案数，乘法原理二者相乘可得
然后 (f(i, j, k, 0) + f(i, j, k, 1) f(i, j, k, 2)) * g(j, k, p) * h(i, T - p) * fac(i) * fac(j) * fac(k) 就是一组方案数
什么意思？
f 确定了每个类型放的位置，然后每个类型的每个物品是不同的，这就是一个多重集排列问题
然后 h 和 t 又确定了选取哪些类型1、2、3，再根据乘法原理乘一块就是答案
2、复杂度
时间复杂度： O(N^3 T)空间复杂度：O(N^ T)
3、代码详解
#include <bits/stdc++.h>
#define sc scanf
using i64 = long long;
using PII = std::pair<int, int>;
constexpr int N = 55, M = 2505, P = 1'000'000'007;void add(int& x, int y) { x += y, (x >= P) && (x -= P); }
int fac[N], f[N][N / 2][N / 3][3], g[N / 2][N / 3][M], h[N][M];void solve() {int n, T;std::cin >> n >> T;fac[0] = 1;for (int i = 1; i <= n; ++ i) fac[i] = 1LL * i * fac[i - 1] % P;std::vector<int> a, b, c;std::vector<std::array<int, 3>> cnt(n);for (int i = 0, t, g; i < n; ++ i) {std::cin >> t >> g;if (g == 1) a.push_back(t);if (g == 2) b.push_back(t);if (g == 3) c.push_back(t);}if (a.size() < b.size())std::swap(a, b);if (a.size() < c.size()) std::swap(a, c);if (b.size() < c.size())std::swap(b, c);int A = a.size(), B = b.size(), C = c.size();// 求费用背包g[0][0][0] = 1;for (int i = 0; i < B; ++ i) for (int j = i; ~j; -- j) for (int p = T - b[i]; p >= 0; -- p)add(g[j + 1][0][p + b[i]], g[j][0][p]);for (int i = 0; i < C; ++ i)for (int j = B; j >= 0; -- j)for (int k = i; k >= 0; -- k)for (int p = T - c[i]; p >= 0; -- p) add(g[j][k + 1][p + c[i]], g[j][k][p]);h[0][0] = 1;for (int i = 0; i < A; ++ i) for (int j = i; ~j; -- j) for (int p = T - a[i]; p >= 0; -- p) add(h[j + 1][p + a[i]], h[j][p]);// 刷表f[1][0][0][0] = f[0][1][0][1] = f[0][0][1][2] = 1;for (int i = 0; i <= A; ++ i)for (int j = 0; j <= B; ++ j)for (int k = 0; k <= C; ++ k) {for (int x = 0, v; x < 3; ++ x) {if (v = f[i][j][k][x]) {if (x) add(f[i + 1][j][k][0], v);if (x ^ 1) add(f[i][j + 1][k][1], v);if (x ^ 2) add(f[i][j][k + 1][2], v);}}add(f[i][j][k][0], f[i][j][k][1]);add(f[i][j][k][0], f[i][j][k][2]);f[i][j][k][0] = 1LL * f[i][j][k][0] * fac[i] % P * fac[j] % P * fac[k] % P;}int res = 0;for (int j = 0; j <= B; ++ j)for (int k = 0; k <= C; ++ k)for (int p = 0; p <= T; ++ p)if (g[j][k][p])for (int i = 0; i <= A; ++ i)if (h[i][T - p])add(res, 1LL * f[i][j][k][0] * g[j][k][p] % P * h[i][T - p] % P);std::cout << res;
}int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifstd::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);int _ = 1;// std::cin >> _;while (_ --)solve();return 0;
}