BZOJ 3594: [Scoi2014]方伯伯的玉米田 (二维树状数组优化DP)

分析

首先每次增加的区间一定是$[i,n]$的形式.因为如果选择$[i,j](j<n)$肯定不如把后面的全部一起加$1$更优.

那么在前$i$个位置用了$j$次操作的话,$a[i]$就变成了$a[i]+j$.
可以列出DP方程式.设$f[i][j]$表示前$i$个用了$j$次操作得到的$LIS$最长的长度. 有
$f[i][j]=Max{ f[k][l]+1 }(lle j 且 a[k]+lle a[i]+j)$那么后面的条件实际上是一个三维偏序(算上编号),这道题数据范围小,直接二维树状数组优化就行了.
时间复杂度$O(nk*log k*log A)$.$A$是最大的$a[i]+k$,空间复杂度是$O(kA)$的.

还能CDQ分治吧…

CODE

#include<bits/stdc++.h>
using namespace std;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
	char ch; int flg = 1; while(!isdigit(ch=getc()))if(ch=='-')flg=-flg;
	for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); res*=flg;
}
const int MAXK = 505;
const int MAXM = 5505;
const int MAXN = 10005;
int n, k, m, T[MAXK][MAXM], a[MAXN];
inline void chkmax(int &x, int y) { if(y > x) x = y; }
inline void upd(int x, int y, int val) {
	for(int i = x+1; i <= k+1; i += i&-i)
		for(int j = y+1; j <= m+1; j += j&-j)
			chkmax(T[i][j], val);
}
inline int qsum(int x, int y) {
	int re = 0;
	for(int i = x+1; i; i -= i&-i)
		for(int j = y+1; j; j -= j&-j)
			chkmax(re, T[i][j]);
	return re;
}
int main() {
	read(n), read(k);
	for(int i = 1; i <= n; ++i)
		read(a[i]), chkmax(m, a[i]);
	m += k;
	int ans = 0;
	for(int i = 1; i <= n; ++i)
		for(int j = k, f_i_j; ~j; --j) {
			chkmax(ans, f_i_j = qsum(j, a[i]+j) + 1);
			upd(j, a[i]+j, f_i_j);
		}
	printf("%d
", ans);
}