网站 可以做无形资产吗,龙岗网站建设哪家便宜,中企动力做的网站后台怎么登陆,给一个网站加上登录界面 如何做目录 一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解 一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
G2 - Playlist for Polycarp (hard version) 二、解题报告
1、思路分析
一…目录 一、题目
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 个类型1j个 类型2k 个类型3并且以类型x结尾且无相同相邻项的方案数
这个dp可太简单了O(1)转移O(N^3 * 3)的方案数很好搞定
再考虑 g(i, j, k, t) 即 选 i 个类型1j个 类型2k 个类型3总费用为t费用指的是时间和的方案数
这是个费用背包问题我们直接求是O(N ^ 4 T)太大了
考虑转换一下g(j, k, p) 为 j个 类型2k 个类型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::pairint, int;
constexpr int N 55, M 2505, P 1000000007;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::vectorint a, b, c;std::vectorstd::arrayint, 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;
}
