题解：AT_s8pc_5_f Lunch Menu

Abczzzzz · 2026-05-11 22:25:18 · 题解

参考 P4766 的思想，想象把最终的序列的笛卡尔树建出来，然后就可以把每个区间挂在一个最大点上了，实际上就是一个分治每个点跨越区间的感觉，就可以 DP 了。下文中默认 a_0=a_{n+1}=10^{9}。

设 f_{i,j,k} 为当前区间为 (i,j)，保留 k 个元素。注意为了使得 (i,j) 符合定义是笛卡尔树上的区间，a_{i-1} 和 a_{i+1} 都默认保留且转移时必须满足 \min(a_{i-1},a_{i+1})\ge a_p，其中 a_p 为枚举的区间最大值。转移比较简单，直接枚举最大值和两边分别的保留个数即可。