HDU 5489 Removed Interval（DP）

题意：求去掉某一个长度为L的子串的LIS

思路：画画图其实比较显然的想法是去掉这个区间的时候答案是右边以第一个数开头的LIS+左边最后一个数小于右边第一个数的LIS，为什么是右边以第一个数开头的LIS呢，因为如果是在这个L的后第二个是最佳答案的话那么我在这个“窗口”滑到L+1这个位置的时候左边会多一个位置，这样答案显然会一样或更优，所以每次只用考虑窗口的右边第一个数的LIS即可，将a[i]取负，然后从后往前做LIS,就是以第i个位置开始的LIS了，然后一边滑窗一边更新左边的LIS更新答案即可

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
#define inf 1e9
int a[maxn],g[maxn],dp[maxn],b[maxn];
int main()
{
    int T,cas=1;
	scanf("%d",&T);
	while(T--)
	{
		int n,L;
		scanf("%d%d",&n,&L);
		for(int i = 0;i<n;i++)
			scanf("%d",&a[i]),b[i]=-a[i];
		for(int i = 0;i<=n;i++)
			g[i]=inf;
		for(int i = n-1;i>=L;i--)
		{
			int x = lower_bound(g,g+n,b[i])-g;
            g[x]=b[i];
			dp[i]=x+1;
		}
        int ans = 0,maxlen = 0;
		for(int i = 0;i<=n;i++)
			g[i]=inf;
		for(int i = L;i<n;i++)
		{
			int x = lower_bound(g,g+n,a[i])-g;
			ans = max(ans,x+dp[i]);
			x = lower_bound(g,g+n,a[i-L])-g;
			g[x]=a[i-L];
			maxlen = max(maxlen,x+1);
		}
		ans = max(ans,maxlen);
		printf("Case #%d: %d\n",cas++,ans);
	}
}