BZOJ 3594 Scoi2014 方伯伯的玉米田树状数组

浏览数：40 / 时间：2015年06月08日

题目大意：给定一个序列，可以选择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;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

BZOJ 3594 Scoi2014 方伯伯的玉米田树状数组