连续段DP

· · 个人记录

CF1515E

设 f_{i,j} 表示开完 i 个电脑，现在有 j 个连续段，转移的话直接扩展连续段，挨着开或者隔一个开，或者合并两个连续段，一次开 2 个或者 3 个，以及新开一个段。

AT_abc313_h

喵喵题。

显然对于确定的 a ，b 的最优方案肯定是对应相同排名的 min(a_i,a_{i+1}) ，设 c_i 为从小到大排序后的 min(a_i,a_{i+1}) ，并将 b_i 从小到大排序，限制转化为 \forall c_i<b_i。

于是将 a_i 从小到大排序，一个一个加入，对于那么先加入的 a_i 肯定作为 c_i 。

DP设 f_{i,j} 表示加入了前 i 个数，有 j 个连续段。则每次可以：

  1. 扩展一个连续段，要满足 a_i<b_i 。

  2. 新开一个连续段，要满足 a_i<b_i 。

  3. 合并两个连续段，没有要求。

AT_arc117_e

喵喵题。

看到这个题，又是括号序列，不难想到前缀和，但是不知道从哪下手。

显然要满足 \sum_x{cnt(x)\choose 2}=k ，其中 x 为前缀和的值，所以不妨在值域DP。

从上往下DP，先只考虑所有的前缀值都大于 0 的情况，假如画个折线图的话就是 x 往上的部分。

设 f_{i,j,k} 表示当前用了 i 个数，构成了 j 个连续段，合法的二元组数为 k 的方案数，每次枚举当前值有多少个 x ，有:

f_{i,j,k}\sum_{x\ge j+1} {x-1\choose j}->f_{i+x,x-j,k+{x\choose 2}}

最后算答案的话枚举 x 上半轴的状态 (i,j,k)，将 sum_p=0 的情况看放到上半轴，于是下半轴的 j'=j-1 ，因为第一段和最后一段属于上半轴，中间夹着下半轴的若干段，其他两个状态互补即可。

P9197

考虑竖着计算贡献，将 f_i 降序排序，DP设 f_{i,j,k,t} 表示放完前 i 个点，当前有 j 个连续段，代价为 k ，以填的端点数为 t ，其中 t\in [0,2] 。

发现无论怎么转移，代价都为 (2j-t)(a_{i}-a_{i+1}) ，即 [a_{i+1},a_{i}] 这段被计算了 (2j-t) 次。

剩下的转移都是套路地扩展/新开/合并。