P5911 [POI2004]PRZ()

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;
}
————————

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;
}