题目链接：HDU4521

【分析】看到了LIS+线段树才会写的，还是太弱；这个其实就是LIS稍微变化了一下，DP方程变成了dp[i] = max{dp[j]}+1 （0 <= j < i-d-1 && a[j] < a[i]）;直接这样做复杂度是O(n^2)的，数据量为10^5，必然超时。看到max{dp[j]}就想到了可以用线段树来优化，用线段树存max{dp[j]}，线段树的区间用a[]的值表示，这样询问[ 0,a[i]-1 ]就保证了a[j] < a[i]，但是由于需要隔开d个位置，所以加入dp[i]的时候更新dp[i+d+1]就保证了[i,i+d]这段还没被加入线段树，这样最后答案就是max{dp[]}。

【AC CODE】421ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
#define id(x,y) ((x)+(y)|(x)!=(y))
const int INF = 0x3f3f3f3f, MAXN = 100000+10;
int mx[MAXN<<1];//线段树维护值(a[])的区间最大的序列长度(dp[])

inline void push_up(int x, int y, int m){
	mx[id(x,y)] = max(mx[id(x,m)],mx[id(m+1,y)]);
}
int p,v;
void update(int x, int y)
{
	if(x == y)
	{
		mx[id(x,y)] = max(mx[id(x,y)],v);
		return;
	}
	int m = (x+y)>>1;
	if(p <= m) update(x,m);
	else update(m+1,y);
	push_up(x,y,m);
}
int ql,qr;
int query(int x, int y)
{
	if(ql <= x && y <= qr) return mx[id(x,y)];
	int m = (x+y)>>1, ans = 0;
	if(ql <= m) ans = max(ans,query(x,m));
	if(qr > m) ans = max(ans,query(m+1,y));
	return ans;
}
int dp[MAXN], a[MAXN];

int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int n,d;
	while(~scanf("%d %d*c", &n, &d))
	{
		int ma = 0;
		rep(i,0,n) scanf("%d%*c", &a[i]), ma = max(ma,a[i]);
		if(d >= n)
		{
			puts("1");
			continue;
		}
		clc(mx,0);
		repe(i,0,d) dp[i] = 1;
		int ans = 1;
		rep(i,0,n-d-1)
		{
			p = a[i];v = dp[i];
			update(0,ma);
			if(!a[i+d+1])
			{
				dp[i+d+1] = 1;
				continue;
			}
			ql = 0, qr = a[i+d+1]-1;
			dp[i+d+1] = query(0,ma)+1;
			ans = max(ans,dp[i+d+1]);
		}
		printf("%d\n", ans);
	}
	return 0;
}