[SCOI2014] 方伯伯的玉米田（树状数组优化 DP）

 loj 传送门https://loj.ac/p/2211

洛谷题目传送门https://www.luogu.com.cn/problem/P3287

解题思路

首先，我们可以贪心地思考一下：对于每一次区间的加一操作，右端点是在末尾会比右端点在中间的情况更好。

因为，当你的右端点在序列中间的时候，相对之下，后面的数就更小了一些，这样是不利于形成上升序列的。

所以，每次的操作右端点应该在末尾，即区间为 。

然后，定义 DP 状态，设  表示前  个数，进行了  次操作，每次操作的左端点都在  之前的最大上升序列长度。

然后考虑如何转移。

首先，从  前找一个点 ，然后枚举这个操作次数 ，可以得到这个转移方程：

其中， 应满足 ，（其中  表示序列的第  项的值）。

但是，这样的转移是  的，那是包会超时的好吧。

所以，我们要考虑优化一下。

我们可以观察转移的范围，，我们对这个范围内的  取的是最大值。

想想，有什么数据结构可以维护这样范围内的最大值？

对，就是（二维）树状数组！

于是，我们可以将第一维表示次数 ，第二维表示 ，这样就可以快速求这个范围内的最大值了。

时间复杂度 

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int a[10001];
int tr[601][5601];
int f[10001][601];
int lowbit(int x)
{
	return x&(-x);
}
int query(int x,int y)
{
	int res=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		for(int j=y;j>0;j-=lowbit(j))
		{
			res=max(res,tr[i][j]);
		}
	}
	return res;
}
void change(int x,int y,int d)
{
	for(int i=x;i<=k+1;i+=lowbit(i))
	{
		for(int j=y;j<=5500;j+=lowbit(j))
		{
			tr[i][j]=max(tr[i][j],d);
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=k;j>=0;j--)//要倒序，避免重复 
		{
			f[i][j]=query(j+1,a[i]+j)+1;
			change(j+1,a[i]+j,f[i][j]);//j可以为0，但是树状数组不行，于是+1处理 
		}
	}
	
	cout<<query(k+1,5500);
	return 0;
}