CF1648D Serious Business
yszs
·
·
题解
传送门
\texttt{Description}
有一个 3 行 n 列的矩阵，第 2 行所有位置无法通过，而第 1 行和第 3 行所有位置都可以通过。
有 q 个可任选的操作，第 i 个操作可以使第 2 行 l_i ~ r_i 个位置可以被通过，代价为 k_i 。
在选择这些操作后，需要从第 1 行第 1 列走到第 3 行第 n 列，且在第 i 行第 j 列只能走到第 i+1 行第 j 列（ i<3 ）或第 i 行第 j+1 列（ j<n ），收益为经过的所有位置的数字之和。
请最大化收益减代价的差，输出这个差。
### $\texttt{Solution}
它走的路径一定是形如三段，有两个断点。
考虑枚举右边的断点，用 \texttt{dp} 处理整体贡献。
设 \texttt{dp[i]} 表示第二个断点在 i。前两段的贡献最大值。
转移考虑每个区间。
有两种情况。( 去掉不选的情况 )
设 s 表示前缀和，v 表示区间的费用。
- 是从左往右第一个区间，也可以理解成第一个断点被包含的区间。
dp[i]=\max_{j=l}^{j<=i} \{s[1][j]+s[2][i]-s[2][j-1]\}-v[t]
2. 是与之前区间接起来的区间。
$$dp[i]=max\{dp[i],dp[l-1]+s[2][i]-s[2][l-1]\}-v[t]$$
考虑每一个 $i$ ，能被哪些 $j$ 转移过来。
对于第二种转移，这是好处理的。
我们把每个 $dp[l-1]-s[2][l-1]$ 当成一个权值，扔到一个堆里。用的时候直接取 $max$ 即可，本质上就是把所有转移点扔进去。
但一个转移点不是一直都会造成贡献的，所以我们在堆里记一个 $r$ 表示生效的区间，$i>r$ 就 $pop$ 掉。
再考虑第一种转移。
难搞的是 $v[t]$，剩下的对区间就没有要求了。
我们把区间的贡献放到 $l$ 处。
这样转移的可以想成：
如果你要选一个转移点 $j$ 转移过来，那么必须要选择一个小于 $j$ 的 $k$，使得 $k$ 是一个区间的左端点。
具体的。
设 $x[j]=s[1][j]-s[2][j-1],y[k]=v[t]
那么我们要找出最大的 x[j]-y[k],k<=j<=i。
类似区间最大子段和，用线段树维护，具体可以看代码。
注意一个位置可能是多个的左端点，那么显然要费用小的。
而且还要支持带修，每个点开一个支持插入删除求最大值的数据结构就行。
我这里用的 set。
然后知道 dp 轻易的就能求出答案。
code