3594: [Scoi2014]方伯伯的玉米田

思路明天过来补。。。

其实很好观察发现到一个性质。要保证单调不下降,每次选择的区间右端点一定是n。

(结果发现了这个性质我还是不会做XD

令f[i][j]表示第i个位置用了j次拔高机会最多保留的个数。

那么f[i][j] = f[x][y] + 1 ( a[i] +  j >= a[x] + y)

考虑树状数组维护,那么 f[i][j] = query(a[i] + j,j + 1) + 1。

注意是j + 1,因为树状数组要保证元素 > 0 ,但是会出现 0 的情况,所以将树状数组整体后移一位;

表示 查询 最大值不超过 a[i] + j ,使用了 j 次机会的情况。

得到的答案再进行更新就好了,搞定。

c++代码如下:

 

8 + 7 =