「SCOI2014」方伯伯的玉米田 - 类LIS

题目大意

    有$n$个数，可以选择一个区间的数使其全部$+1$，最多执行$k$次这样的操作，求最大可能的最长不下降子序列。

---

题目分析

考虑一个贪心策略：每次选择的区间一定是原序列的一个后缀。
证明显然。

这样，我们可以设$f[i,j]$表示到第$i$个数，使用了$j$次拔高的操作，所得到的最大的$LIS$。

可以列出方程：

$$f[i,j]=\max_{k\lt i,d\lt j}f[k,d]+1\quad(a[k]+d\le a[i]+j)$$

我们发现了一个三维偏序的关系，转移方程是广义LIS的形式。
直接上cdq分治！
题目数据范围小，使用二维树状数组维护最优解即可。
时间复杂度$O(nk\log k\log(\max a_i+k))$。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=10005,maxk=505,maxv=5005;

int n,k,a[maxn],f[maxn][maxk],Max=0,ans=0;

struct BIT {
	int c[maxv+maxk][maxk];
#define lowbit(x) x&-x
	void add(int x,int y,int v) {
		y++;
		for(int i=x; i<=Max; i+=lowbit(i))
			for(int j=y; j<=k+1; j+=lowbit(j))
				c[i][j]=max(c[i][j],v);
	}
	int sum(int x,int y) {
		y++;
		int sum=0;
		for(int i=x; i>=1; i-=lowbit(i))
			for(int j=y; j>=1; j-=lowbit(j))
				sum=max(sum,c[i][j]);
		return sum;
	}
} bit;

int main() {
	n=Get_Int();
	k=Get_Int();
	for(int i=1; i<=n; i++) {
		a[i]=Get_Int();
		Max=max(Max,a[i]);
	}
	Max+=k+1;
	for(int i=1; i<=n; i++) {
		for(int j=0; j<=k; j++) {
			f[i][j]=bit.sum(a[i]+j,j)+1;
			ans=max(ans,f[i][j]);
		}
		for(int j=0; j<=k; j++)bit.add(a[i]+j,j,f[i][j]);
	}
	printf("%d\n",ans);
	return 0;
}