标题效果：给定一个序列，能够选择k次每个部分的数量和在范围内+1，寻求操作后LIS最大值

我的做法是不是一个标准的解决方案。

。。5E为什么跑飞的复杂性。

。

。

首先，显而易见的结论是，我们选择k右端点都是n时才干保证最优

知道这个我们就能够DP了- -

令f[i][j]表示前i个数上升j次的最大LIS

那么有f[i][j]=max{f[k][l]|k<i,l<=j,a[k]+l<=a[i]+j}+1

看到三维偏序就能够用二维树状数组了- -

时间复杂度O(nklog(max(ai)+k)logk)

这复杂度跑的飞起真是醉了。。。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define M 10100

using namespace std;

int n,k,max_num,ans,a[M];

namespace BIT{

	int c[6060][550];

	void Update(int x,int y,int val)

	{

		int i,j;

		for(i=x;i<=max_num+k;i+=i&-i)

			for(j=y;j<=k+1;j+=j&-j)

				c[i][j]=max(c[i][j],val);

	}

	int Get_Ans(int x,int y)

	{

		int i,j,re=0;

		for(i=x;i;i-=i&-i)

			for(j=y;j;j-=j&-j)

				re=max(re,c[i][j]);

		return re;

	}

}

int main()

{

	using namespace BIT;

	int i,j;

	for(cin>>n>>k,i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

		max_num=max(max_num,a[i]);

	}

	for(i=1;i<=n;i++)

		for(j=k;~j;j--)

		{

			int temp=Get_Ans(a[i]+j,j+1)+1;

			ans=max(ans,temp);

			Update(a[i]+j,j+1,temp);

		}

	cout<<ans<<endl;

	return 0;

}