[SCOI2014] 方伯伯的玉米田：单 \(\log\) 做法比较 educational。
首先考虑一个暴力 DP：\(dp_{i, j, k}\) 表示以 \(i\) 的元素结尾，用了 \(j\) 个区间加，LIS 的最后一个元素为 \(k\) 的 LIS 长度。
进一步观察性质，发现每次区间加的右端点为 \(n\) 一定是最优的。用调整法容易证明，如果一个区间加的右端点没有延伸到 \(n\)，那么可能在未被区间加的地方就不能继承前面的 LIS 了。
因为区间加会一直延伸到 \(n\)，所以有式子：\(k = a_i + j\)，DP 状态就被我们省掉了一维。
然后转移是平凡的，式子如下：
注意到这是个三维偏序的转移，所以直接上 CDQ 优化大概就能过了。但是我们转移的时候已经是按顺序转了 \(i\) 的，因此只要考虑后面的二维偏序即可。而又因为后面两维值域较小，所以直接用二维树状数组维护即可。时间复杂度 \(O(nk\log n\log k)\)。
考虑如何优化掉一个 \(\log\)。注意到这三维都是根据其前缀的信息转移，所以考虑对前缀转移的一个常见 trick：状态设计优化为存储其前缀的所有信息。在本题中，就体现为 \(dp_{i,j, k}\) 表示对于前 \(i\) 位，用了不超过 \(j\) 个区间加，LIS 的最后一个元素不超过 \(k\) 的 LIS 长度。因为 \(k\) 的等式在此时不成立了，所以不能省略 \(k\) 的一维。
用了前缀优化状态后，转移显然从 \(dp_{i-1, j-1,k},dp_{i-1, j, k-1}\) 得到。考虑优化最后一维，发现在前两维确定后，如果 \(i\) 要成为 LIS 中的元素，那么可以直接从前面转移了的 DP 值中选择 \(k \le a_i + j\) 的 DP 值；否则直接从前面的继承过来就行。因此我们可以把 \(k\) 这一维放在树状数组上，只有在 \(i\) 为 LIS 元素的时候才从树状数组上转移，否则直接继承前面的状态即可。
对于省略 \(k\) 可以这么理解：在第二种情况中 \(k\) 其实是不发生任何改变的，而只有第一种情况中 \(k\) 才会对转移产生影响。省略 \(k\) 相当于把原来的 DP 数组拆成了两个，一个是第一种情况的 DP 值，一个是第二种情况的 DP 值。因为第一种情况也只会从第一种情况转移，所以第一种情况内部使用树状数组存 \(k\) 那一维的 DP 值即可。
时间复杂度 \(O(nk\log (a_i + k))\)。
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 10005, K = 505;
int n, m, dp[N][K], a[N];
int lowbit(int x)
{return (x & (-x));
}
struct BIT{int tr[N];void update(int p, int v){p++;while(p < N){tr[p] = max(tr[p], v);p += lowbit(p);}}int query(int p){int res = 0;p++;while(p){res = max(res, tr[p]);p -= lowbit(p);}return res;}
}tra[N], trb[N];
int main()
{// freopen("P3287.in", "r", stdin);// freopen("P3287.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++){for(int j = m; j >= 0; j--){dp[i][j] = max(tra[j].query(a[i] + j), trb[a[i] + j].query(j)) + 1;tra[j].update(a[i] + j, dp[i][j]);trb[a[i] + j].update(j, dp[i][j]);}for(int j = 0; j <= m; j++)dp[i][j] = max(dp[i - 1][j], dp[i][j]);}cout << dp[n][m];return 0;
}