Codeforces 739E:Gosha is hunting – 题解

主要思路

一眼可以看出一个 \(\Theta(n^3)\) 的 DP。其实用双带权二分就可以用 \(\Theta(n \log^2 n)\) 的时间搞了,但是我没写这个写法。

考虑一下被选择时的贡献。\(p_a, p_b\) 是单元贡献,考虑同时被选的贡献 \(1 – (1 – p_a)(1 – p_b) = p_a + p_b – p_a p_b\)。所以我们可以考虑最大费用最大流,来算这个式子。

需要注意的是,我们需要保证每一次代价都是正的,因为我们其实并不需要最大流,而只是相对的最大费用。

继续阅读Codeforces 739E:Gosha is hunting – 题解

[Libre OJ]6014「网络流 24 题」最长 k 可重区间集题解

主要思路

这道题还是很妙的,我只想到了最大费用最大流之后就想不动了。

我们在这里介绍边数为\(O(n)\)级别的解法。考虑把所有的端点离散化为\(2n\)个连续的点,然后相邻端点\(i, i+1\)相互连接流量无限、费用为零的边。考虑区间左右端点,左端点连到右端点,流量为\(1\),费用为区间长度。最后源点连左端点,汇点连到右端点。

这样就可以强制满流,且费用最大。

继续阅读[Libre OJ]6014「网络流 24 题」最长 k 可重区间集题解