9.25 T3 蜜蜂搬家

Vision271 · 2022-09-26 17:16:42 · 个人记录

题意

• 你可以在 [1,L] 中自由选出任意个区间（左右端点自己决定，但不能相交）。

• 设你选出了 K 个区间，则要支付 K\times w+\sum\limits_{i=1}^K (r_i-l_i+1)\times c 的代价，即 \text{段数}\times w+\text{长度}\times c。

• 在 [1,L] 范围内本身有 n 个区间 [l_i,r_i](可能相交)，每个区间的价值为 v_i（可能为负数）。

• 当且仅当该区间被你选的区间的并集完全包含，你获得其价值。

• 特别地，如果第 i 个给出的区间分属于 num 个你选出的区间（不管是否成功获得其价值），则你要支付额外的 (num-1)\times max(0,v_i) 的代价，即 \text{分割次数} \times max(0,v_i) 的代价。

• 特别地，有些区间必须被完全包含；有些区间的 num 只能为 0 或 1。

• 求最大总价值，即总价值-总代价。

数据范围

分析

• 我们看到这道题的限制一抹多啊，堪称是限制上长了个决策。

• 我赛时的想法是推性质，即尝试找到决策的逻辑（来避过一些限制），譬如被带走的区间不可能被分割（因为可以将相连区间合并），...

• 不过赛后看来，虽然并不错，但也并不明智。这样总归不太解得出来题。

• 快刀斩乱麻。不论如何，这种东西看起来就长得很像前缀线段树或者 DP（遇事不决 DP 一下试试），考虑到线段树毕竟只是个辅助，我们尝试设计 DP 状态（先抛开特殊限制）：

  • 状态设计：dp_i 表示考虑完 1\sim i 的最大价值。

  • 初始化：dp_0=0。

  • 状态转移方程：既然是考虑完而非带走完，显然它单调，而且可以摆烂不要某一段。故，转移方程如下：

  • 依次是区间价值，即 val(j,i)，然后是区间长度费用，然后是区间个数费用，然后是分割区间费用，即 cost_i 表示在 i 后面分割一下的费用。

  • tips：这里之所以把左右的分割代价都算上是对的，正是因为不可能有相连的区间（否则合并更优），所以它只劣化了非最优解，不影响。

• 显然这个东西朴素转移是 O(n^2) 的，我们得设法 O(\log) 地找前缀最大值（不是前缀线段树那种，毕竟这里不互相影响）。

• 于是考虑拆东西，显然 -(i+1)\times c,cost_i,w，都可以提出来（cost 可以考虑用个线段树预处理一下），现在里面还剩 dp_j+val(j,i)+j\times c-cost_{j-1}。

• 如果这个东西能上线段树多好啊，那就可以快速查最值了。cost 和 c 还有 dp 显然可以暴力 ins 进去，但是 val(j,i) 怎么办？

• 略作转化：某个区间被完全包含（上面证明了不可能分块带走了），一定是 j\leqslant l \And i\geqslant r。

• 于是有一个很妙的操作：准备计算 dp_i 的时候，先把所有 [l,i] 的价值都扔到线段树的 [1,l] 上去。

• 解决。

• 特殊限制？嗯...第一种把 v 赋成正无穷最后减回来，第二种把那个分割代价赋成正无穷。