做题记录 26.1.25

· · 个人记录

\textcolor{black}\odot P5244 [USACO19FEB] Mowing Mischief P

等价于选择点的一个子集并重排序，要求横纵坐标都不降，最大化点集大小后最小化

将点集以 x 为第一关键字，y 为第二关键字升序排序，设 (x_i,y_i) 为排序后的结果

令 ln_i 表示以 (x_i,y_i) 结尾的点序列的长度的最大值，即 \{y\}_{j=1}^i 的最长不降子序列，容易 O(n\log n) 求出

令 dp_i 表示到 (x_i,y_i) 的答案，则

dp_i=\min_{j<i,x_j\le x_i,y_j\le y_i,ln_j+1=ln_i} dp_j+(x_i-x_j)(y_i-y_j)

按 ln 分层，则只会在相邻层之间转移

相邻两层之间，下一层从上一层的一个区间转移，建立线段树，转化为一个区间向下一层若干位置转移

可证具有决策单调性，容易分治优化

时间复杂度 O(n\log^2 n)

代码

参考

\textcolor{black}\odot AT_agc017_f [AGC017F] Zigzag

轮廓线 dp，令 dp_{i,j,s} 表示填到 (i,j)，轮廓线状态为 s，其中 s 在 i 行上的部分描述已经填的状态，在 i-1 行的部分描述对第 i 行的约束

容易做到 O(nm2^n)

代码

参考