Description 方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。 这排玉米一共有N株，它们的高度参差不齐。 方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。 方伯伯可以选择一个区间，把这个区间的玉米全部拔高1单位高度，他可以进行最多K次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。

[BZOJ3594] [Scoi2014]方伯伯的玉米田 题目大意 给定长度为 n n的一个序列,可以找出kk个区间使这 k k个区间的元素同时+1+1,询问最后最长不下降子序列的大小 n≤104,k≤500,ai≤5000 n\le10^4,k\le 500,a_i\le5000 题解 一个结论:找出的区间的右端点一定是 n n dp[i,j]=max{dp[k,l]}+1

f[i][j]表示到第i位，使用了j次机会的最长不下降子序列长度 转移：f[i][j]=max(f[x][y])+1; x<i; y<=j; a[x]+y<=a[i]+j; 所以根据后两个条件维护二维树状数组求最值 #include<cstdio>#include<cstring>#include<iostream>using namespace std;int n,m,k;