PRZ —— Pixel Rebelz(?
传送门
哈哈!
思路
预处理 $ T_i $ 以及 $ W_i $ ,为状态为 $ i $ 时不分组直接过(管他压不压断桥)的时间和总重量。
然后 $ f_i $ 就是过桥状态为 $ i $ 时的最优解。
枚举 $ i $ 的子集 $ j $ ,如果 $ j $ 这组能单独过桥,那就让他们过试试(以及 $ i $ 其他人组建一组)。
所以状态转移方程就是 $ f_i = \min \{ f_i, T_j + f_{i \oplus j} \} (W_j \leq W)$ 。
好!
代码
#include <bits/stdc++.h>
using namespace std;
int f[1 << 20], T[1 << 20], W[1 << 20];
int t[20], w[20];
int main() {
int k, n;
scanf("%d %d", &k, &n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &t[i], &w[i]);
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 0; i < (1 << n); i++){
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
T[i] = max(T[i], t[j]);
W[i] += w[j];
}
}
}
for (int i = 0; i < (1 << n); i++) {
for (int j = i; ; j = i & (j - 1)) {
if (W[j] <= k) {
f[i] = min(f[i], T[j] + f[i ^ j]);
}
if (!j) {
break;
}
}
}
printf("%d", f[(1 << n) - 1]);
return 0;
}
标签:状态,传送门,POI2004,P5911,过桥,PRZ
From: https://www.cnblogs.com/AProblemSolver/p/16923579.html