HDU 5489 Removed Interval 2015 ACM/ICPC Asia Regional Hefei Online (LIS变形)

定义f[i]表示以i为开头往后的最长上升子序列,d[i]表示以i为结尾的最长上升子序列。

先nlogn算出f[i],

从i-L开始枚举f[i]，表示假设i在最终的LIS中，往[0,i-L)里找到满足ai>aj中dj值最大的。用dj+f[i]更新。

但是这样会少考虑一种情况，即i-L以后都不在最终的LIS里面，这样一定是以[0~i-L)中的某个结尾的，所以还要用d[j]去更新答案。

#include<bits/stdc++.h>
using namespace std;


const int maxn = 1e5+5;
int a[maxn];
int g[maxn];
int f[maxn];

const int INF = 0x3f3f3f3f;

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int T; scanf("%d",&T);
    for(int ks = 1; ks <= T; ks++){
        int N,L,k ; scanf("%d%d",&N,&L);
        for(int i = 0; i < N; i++) scanf("%d",a+i);
        fill(g+1,g+N-L+1,-INF);
        for(int i = N-1; i >= L; i--){
            k = lower_bound(g+1,g+N-i,a[i],greater<int>())-g;
            f[i] = k;
            g[k] = a[i];
        }
        memset(g+1,0x3f,sizeof(int)*(N-L));
        int ans = 0;
        for(int i = L; i < N; i++){
            k = lower_bound(g+1,g+i-L+1,a[i])-g;
            ans = max(k-1+f[i],ans);
            k = lower_bound(g+1,g+i-L+1,a[i-L])-g;
            ans = max(k,ans);
            g[k] = a[i-L];
        }
        printf("Case #%d: %d
",ks,ans);
    }
    return 0;
}