hdu 5489

题意：给出一个长度为n的数列，删去长度为l的子数列，问最长严格上升子序列

思路：我们可以求出每个数字以他为起点的上升序列长度q[i]，然后我们可以得到在我这个数字a[i]在i-m之前的那些数的上升序列排第K个，那么就是K-1+q[i]。然而开始我求q[i]的时候，是这样想的，先求一遍正的LIS,最长长度为Max,那么q[i]=Max-他在子序列排第几位+1,WA到死，比如 5 7 6 4 9 ，4在第一位，9在第3位，然而以4为起点只有长度2

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int INF=1e9+10;

int a[N],b[N];
int z[N],q[N];
int dp[N];

int main(){
    int t;
    int n,m;
    int k=1;
    scanf("%d",&t);
    while(t--){
        int Max=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) {scanf("%d",&a[i]);b[i]=-a[i];dp[i]=INF;}
        for(int i=n;i>=1;i--){
            int k=lower_bound(dp+1,dp+1+n,b[i])-dp;
           // cout<<b[i]<<" "<<k<<endl;
            q[i]=k;
            dp[k]=b[i];
        }
         Max=0;
         int y=0;
         for(int i=1;i<=n;i++) dp[i]=INF;
         for(int i=1;i<=n-m;i++){
             int k=lower_bound(dp+1,dp+1+n,a[i+m])-dp;
             Max=max(Max,k-1+q[i+m]);
              k=lower_bound(dp+1,dp+1+n,a[i])-dp;
             dp[k]=a[i];
             y=max(y,k);
         }
         Max=max(Max,y);
         printf("Case #%d: %d
",k++,Max);
    }
    return 0;
}