首页 > 其他分享 >P5911 [POI2004]PRZ

P5911 [POI2004]PRZ

时间:2022-11-24 22:00:58浏览次数:76  
标签:状态 传送门 POI2004 P5911 过桥 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;
}

标签:状态,传送门,POI2004,P5911,过桥,PRZ
From: https://www.cnblogs.com/AProblemSolver/p/16923579.html

相关文章

  • P5914 [POI2004]MOS 题解
    题目传送门分析这是一道小学经典的数学题,对于这种求最短时间的题目,我们要认真考虑两组人员:首先,跑的快的人应当跑的最多,能者多劳。其次,跑的慢的人应当跑的最少,否则会拉......
  • P5911 [POI2004]PRZ——状压dp
    一样,从\(n\le16\)启发用状压dp思路本质上与UVA11825Hackers'Crackdown异曲同工,不过可以通过预处理处理出一组人的集合时间复杂度最坏为\(O(2^{2n})\),当任何一个集合......