做题记录 25.8.24
szt100309
·
·
个人记录
\purple\odot CF1566F Points Movement
先将 a 从小到大排序
去除与一个 a_i 有交的线段，对于一组互相包含的线段保留最内层的
显然剩下的所有线段两端点都递增且属于一个空隙 (a_{i-1},a_i)（假定 a_0=-\infty,a_0=\infty）
显然最优情况为每个 a_i 选出 l_i\le a_i\le r_i，所有 a_i 的 [l_i,r_i] 无交，且每条线段都与某个 [l_i,r_i] 有交，一个 a_i 的代价为 r_i-l_i+\min(a_i-l_i,r_i-a_i)
令 f_{i,0/1} 表示考虑 l_{1\sim i} 和 r_{1\sim i-1}，他们的最小总代价，且 a_i 先走到 l_i/r_i
对于一组空隙 a_{i-1},a_i，设其中的线段依次为 [l_i,r_i]\mid 1\le i\le k，令 L=a_{i-1}+l,R=r+a_i（此处 + 表示拼接），转移为
\forall x,l\gets L_x-a_{i-1},r\gets a_i-R_x:\\
f_{i-1,0}+l+2r\to f_{i,0}\\
f_{i-1,1}+2l+2r\to f_{i,0}\\
f_{i-1,0}+l+r\to f_{i,1}\\
f_{i-1,1}+2l+r\to f_{i,1}
时间复杂度 O(\sum(n\log n+m\log m))
代码
参考
\blue\odot CF1562E Rescue Niwen!
令 lcp_{i,j}=\text{lcp}(s_{i\sim n},s_{j\sim n})
当选择 [l,r] 时，必然存在一种最优解使得 [l,r+1\sim n] 依次被选
证明：
- 若最优解中 [l,r] 被选，且 [l,r+1] 没有被选，则说明 [l,r] 下一个被选的元素 [i,j] 满足 [l,r]<[i,j]\le [l,r+1]
- 若 [i,j]=[l,r+1] 则可视为选择了 [l,r+1]
- 若 j-i>r-l+1，则可在 [l,r] 和 [i,j] 之间插入 [i,j-1]，当前情况不是最优的
- 显然 j-i\ge r-l+1，当 j-i=r-l+1 时，必有 [l,r]=[i,j-1]，此时可视为选择了 [i,j-1],[i,j]
- 归纳可得原结论成立
令 f_i 表示最后一个选了 [i,n] 时的 \text{LIS}
转移为
f_i=\max\left(n-i+1,\max_{j<i,s_{j+lcp_{i,j}}<s_{i+lcp_{i,j}}}(f_j+n-(i+lcp_{i,j})+1)\right)
时间复杂度 O(\sum n^2)
代码
参考