hdu 5489——Removed Interval——————【删除一段区间后的LIS】

Removed Interval

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1086 Accepted Submission(s): 392

Problem Description

Given a sequence of numbers

Input

The first line of input contains a number

Output

For each test case, output a single line consisting of “Case #X: Y”.

Sample Input

5 2

1 2 3 4 5

5 3

5 4 3 2 1

Sample Output

Case #1: 3

Case #2: 1

Source

2015 ACM/ICPC Asia Regional Hefei Online

题目大意：给你n个元素的序列。让你移除长度为L的一段区间，让剩下的元素所形成的LIS最大。

解题思路：枚举删除区间。同时更新删除区间后能形成的LIS最大值。并且每次更新删除区间的前面能形成的LIS。。。。。。。。。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+200;
const int INF = 0x3f3f3f3f;
int a[maxn],b[maxn],endminv[maxn];
int dp[maxn];
int BinSearch(int l,int r,int key,int typ){ //二分求解小于等于key的第一个位置
    int md;                                 //二分求解大于等于key的第一个位置
    if(typ==0){
        while(l<r){
            md=(l+r)/2;
            if(endminv[md]>key){
                l=md+1;
            }else if(endminv[md]<key){
                r=md;
            }else{
                return md;
            }
        }
        return l;
    }else{
        while(l<r){
            md=(l+r)/2;
            if(endminv[md]>key){
                r=md;
            }else if(endminv[md]<key){
                l=md+1;
            }else{
                return md;
            }
        }
        return l;
    }
}

int main(){
    int T,n,L,cnt=0;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&L);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=0;i<=n;i++)
            endminv[i]=-INF;
        for(int i=n;i>=1;i--){  //逆序得到最长递减子序列，那么正序依然是递增的
            int x=BinSearch(1,n,a[i],0);
            endminv[x]=a[i];
            dp[i]=x;    //以a[i]结尾的最长递减子序列长度
        }
        memset(endminv,INF,sizeof(endminv));
        int ans=0;  int len=1;
        for(int i=L+1;i<=n;i++){    //枚举要删除的区间的右端点
            int x=BinSearch(1,n,a[i],1);
            ans=max(ans,dp[i]+x-1);//删除区间后前后能拼接成的LIS长度
            x=BinSearch(1,n,a[i-L],1);  //枚举区间左边能形成的LIS
            endminv[x]=a[i-L];
            len=max(len,x+1);   //对于区间左边正常求LIS
        }
        printf("Case #%d: %d
",++cnt,max(ans,len-1));
    }
    return 0;
}