组合数学+费用背包+刷表，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;
}