Sol两个限制的导弹拦截。设\(f_i\)表示以\(i\)结尾的最长LIS显然可以得到暴力转移方程\(f_i=\displaystyle\max_{j=1,a_j\gea_i,b_j\geb_i}^{i-1}f_j+1\)，考虑到是三维偏序，所以用CDQ分治优化即可。离散化不要忘记排序！Code#include<iostream>#include<iomanip>

这是CDQ分治优化1D/1D动态规划的模板题（1D/1D动态规划的概念见OI-wiki）一般来说，优化的1D/1D/动态规划，在转移的时候是由不等式作为条件的，所以可以像这样转化为三维偏序用线段树进行如下维护：1.维护区间最大值2.查询区间最大值的某一数组的和代码见下（一定要学会将数组翻转的操作）#

题目概述：有一套导弹拦截系统，其每次可以拦截的导弹高度都不能高于上一次拦截导弹的高度。现在有一些导弹飞来，问这套系统最多能够拦截多少导弹，若想拦截所有的导弹，最少需要多少套系统。解题思路：第一问就是典型的LIS模型。第二问的关键在于将某枚导弹归为哪一类下降子序列，从而使得使

【题目】某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。输入导

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

拦截导弹题目大意给定若干元素，每个元素有\(3\)个属性\(t_i,h_i,v_i\)，求出一个使得对于\(\foralli,j,i>j\)，\(t_i>t_j,h_i\leh_j,v_i\lev_j\)均成立的最长的子序列\(a\)的长度。并计算每个元素在所有的可能的\(a\)方案中的出现概率。思路分析先看第一个问题：按\(

拦截导弹贪心策略如下所示：图一表示具体做法，图二表示证明上图的证明是指，如果最优解和贪心存在第一个地方不一样，那么因为\(a\)是\(\gex\)的最小数，所以\(b\gea\)，所以这两段是可以互换的，所以最优解是可以变成贪心的。性质，\(g\)数组单调不降，证明如上图。我们可以惊奇的