细节好多,写死人了。
题意简述
有 $n$ 个二元组 $(a_i, l_i)$ ,对于每个二元组有两个选择:将数轴上的 $[a_i - l_i, a_i]$ 染色或将 $[a_i, a_i + l_i]$ 染色。求最大化的最终被染色总长度。输入均为整数, $1\le n\le 100, 0\le a_i\le 10^8, 1\le l_i\le 10^8$ ,保证 $a_i$ 互不相同。
主要思路
先把二元组按 $a_i$ 排序,考虑动态规划,设 $f(x, s), x\in[1, 2n], s\in[0, 1]$ 表示「第 $x$ 个二元组向左($s=1$)或右($s=0$)贡献,最终染色总长度与 $(-\infty, a_i - s\times l_i]$ 的交的最大值」。
先考虑第 x 个二元组向左贡献。则 $[a_x - l_x, a_x]$ 这段区间内的所有二元组,也都会向左贡献,这会产生连锁反应。连锁反应过后,我们可以得到最右边的不被连锁反应影响的二元组 $y$ 。此时便转化为一个子问题,然而多了一个右端点的限制,但是总体区别不大。
然后考虑这个二元组往右贡献。发现其实更简单,因为不会产生连锁反应,所以不被影响的最右的二元组即为 $x - 1$ 。所以无论左右的转移代价都是常数。
有 $O(n)$ 中状态,而每种状态的转移方式不会超过 $O(n)$ 种,转移代价为常数,总复杂度 $O(n^2)$ 。
参考代码
1 |
|