主要思路

一眼可以看出一个 \(\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\)。所以我们可以考虑最大费用最大流，来算这个式子。

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

主要思路

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

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

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

Continue reading →