「题解」[SDOI2011]拦截导弹 & [HEOI2016/TJOI2016]序列
（因为是一类题写成一篇题解了）
[SDOI2011]拦截导弹
link
\(dp_i=\max_{j=1}^{i-1}\{dp_j[h_j\geqslant h_i,v_j\geqslant v_i]\}+1\)
考虑只有 \(h_i\) 或 \(v_i\) 其中一个限制时，果断用树状数组/线段树（其实 cdq 也可以）维护。多加一个限制，刚好 \(\{i,h_i,v_i\}\) 构成了三元组，发现在进行三维偏序时做 dp 即可。
代码有几个细节：
- 先跑 \(cdq(l,mid)\)，再进行 dp，然后跑 \(cdq(mid+1)\)
- 初始值可以在 \(l=r\) 时赋，也可以在进行 cdq 前赋。两种都挺方便的。
[HEOI2016/TJOI2016]序列
link
令 \(mn_i\) 为 \(i\) 能取到的最小值，\(mx_i\) 为最大值，\(a_i\) 为初始值。
定一个规则贪心地选择是很困难的。\(dp_i=\max\{dp_j+1[mn_i\geqslant a_j,a_i\geqslant mx_j]\}\)。
乍一看是三个限制（\(mn,a,mx\)），但是每次只用得到两个。所以还是像上一题一样做即可。但是此题需要将一个拆成转移点（\((i,a,mx)\)）和答案点（\((i,mn,a)\)）。