luogu上刷到���P1020 [NOIP1999 提高组] 导弹拦截和P1439 【模板】最长公共子序列 有感
（）LIS：Longest Increasing Subsequence，最长递增子序列
给定一个字符串，求出最长递减序列
这个题问的是下降，上升情况反过来就好了
（）只考虑第一问，由于O（n*n）会爆T（不解释了），考虑压缩时间
还记得在网上看到的一句话
如果需要对dp进行时间优化，不妨交换状态参数和状态量
基于这句话的启发，这个题思路就若隐若现了
步骤一：首先我们很容易想到 dp[ i ] 来表示：前i个数中以第i个数结尾的最长递减序列
这句话中我理解的状态参数就是（以第i个数结尾）状态量就是（最长递减序列）
我们不妨构造 f 数组，f [ i ] 代表长度为 i 的递减序列的最后一个数的最大值
（为什么要怎么做，等会解释，先理解成最大值后面才能放更多小的数使序列更长）
这个时候状态参数就是（长度为 i 的递减序列）状态量就是（结尾的最大值）
这样我们就实现了递减序列和结尾数字的交换（前面可以再看一遍）
步骤二：需要一个前提证明，f 数组是单调递减的（其实是单调不递增，为了不拗口先这么叫）：
反证一下，如果 f [x+1] > f [x] 也就是说长度为x+1的递减序列的末尾会大于长度为x的，那就不对了，由于序列递减，这个长度为x+1的序列的第x个数（称作a）一定>=第x+1个数（称作b），那长度为x的序列结尾的数至少就会跟这个a相等，也就是发 f [ x ] >=a，由于a>=b，b=f [ x+1 ]，则 f [x] > f [x+1]得证。要是被绕了就看看这个例子：
长度为4的递减序列：9 6 3 2 ，如果长度为3的递减序列末尾比2还小就会冲突，因为这个序列至少可以取到9 6 3，这个最大值至少比3还大，也就不可能小于2了
步骤三：dp [ i ] 和 f [ i ] 同步进行计算，相互更新，计算dp[ i ] 需要对于每一个 i 满足：
想要用第i 个数结尾，前面的结尾必须比第i个数还大，但是前面满足的递减序列又要尽可能长，也就是i尽可能大，但是 f [ i ] 要比第i个数小，直接二分找到答案。（f 数组求dp数组）
每次计算完 dp [ i ] ，设这个长度为k， 也就是dp [ i ]=k，那么 f [ k ] 长度为k的递减序列的末尾就要尝试更新为第 i 个数。（dp 数组更新 f 数组）
最后遍历看看以谁结尾的最长递减序列最长就好了
AC代码如下（fun2函数是第二问的请忽略，后面的循环和ans数组也是）：
//动态规划的时间优化
#include
#define N 100050
using namespace std;
typedef long long ll;
vectorans;
ll h[N],dp[N],f[N];
ll fun(ll i){
ll l=0,r=N-1;
while(l=h[i]){//等于的情况要特殊考虑！！！
l=mid;
}else{
r=mid;
}
}
if(f[r]>=h[i] && h[i]){
return r;
}else{
return l;
}
}
void fun2(ll i){
if(ans.size()==0){
ans.push_back(i);
}else if(ans.size()==1){
if(ans[0]>=i){
ans[0]=i;
}else{
ans.push_back(i);
}
}else{
ll l=0,r=ans.size()-1;
while(li){
r=mid;
}else{
l=mid;
}
}
if(ans[l]>=i){
ans[l]=i;
}else if(ans[r]>=i){
ans[r]=i;
}else{
ans.push_back(i);
}
}
}
int main(){
ll n=1;
while(cin>>h[n]){
n++;
}
n--;
dp[1]=1;
f[1]=h[1];
for(int i=2;i 
