复杂度 \(O(n^2k^2)\)，期望得分 \(0\text{pts}\)。

考虑优化。
观察状态转移方程，发现 \(f_{k,l}\) 是满足 \(1\le k 的一个三维前缀最大值。
\(i\) 维可以通过枚举消除，问题变为二维前缀最大值问题。

考虑二维树状数组优化。
修改状态，设 \(f_{j,k}\) 为 \(1\sim i-1\) 中，被不超过 \(j\) 个修改区间覆盖，结尾 \(\le k\) 的最长不下降子序列的长度。
直接用树状数组维护 \(f\) 即可。

注意 \(j\) 可以为 \(0\)，树状数组的 \(j\) 维整体右移一位， \(j+1\) 实际上表示使用了 \(j\) 次修改。

由于通过枚举消除了 \(i\)，为防止重复更新，套用01背包的思想，\(j\) 需要从大到小枚举。

复杂度 \(O(nk\log n\log k)\)，期望得分 \(100\text{pts}\)。

神仙提出的单 \(\log\) 写法：

观察状态的含义：
\(f_{j,k}\) 为 \(1\sim i-1\) 中，被不超过 \(j\) 个修改区间覆盖，结尾 \(\le k\) 的最长不下降子序列的长度。
发现 \(j\) 固定时，\(f_{j,k}\) 随 \(k\) 增加，只增不减。
发现 \(k\) 固定时，\(f_{j,k}\) 随 \(j\) 增加，只增不减。

则树状数组中 \(x\le j,y\le k\) 的最大值，一定会在第 \(j\) 行/ 第 \(k\) 列取到。

考虑建立 \(2\) 个 \(n\) 行的一维树状数组，分别维护每行/每列的 \(f\) 值，更新时更新 整行/整列 有下图形式：

复杂度 \(O(nk\log n)\)，期望得分 \(100\text{pts}\)。

代码实现

\(O(nk\log n)\)

写的比较丑连 \(4s\) 都进不去 /kk

//知识点:DP，树状数组
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#define ll long long
#define lowbit(x) (x&-x)
const int kMaxn = 1e4 + 10;
const int kMaxk = 510;
const int kMaxv = 5010;
//=============================================================
int n, K, ans, a[kMaxn], t1[kMaxk][kMaxv], t2[kMaxk + kMaxv][kMaxk];
int maxx, maxy;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void GetMin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
int Query(int *x, int pos) {
  int ret = 0;
  for (int i = pos; i; i -= lowbit(i)) {
    GetMax(ret, x[i]);
  }
  return ret;
}
void Modify(int *x, int pos, int lim, int val) {
  for (int i = pos; i <= lim; i += lowbit(i)) {
    GetMax(x[i], val);
  }
}
//=============================================================
int main() {
  n = read(), K = read();
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    GetMax(maxy, a[i]);
  }
  maxx = K + 1, maxy += K;

  for (int i = 1; i <= n; ++ i) {
    for (int j = 0; j <= K; ++ j) {
      int tmp = Query(t1[j], a[i] + 1) + 1;
      GetMax(tmp, Query(t2[a[i] + j], j + 1) + 1);
      GetMax(ans, tmp);
      Modify(t1[j], a[i] + 1, kMaxv, tmp);
      Modify(t2[a[i] + j], j + 1, K + 1, tmp);
    }
  }
  printf("%d\n", ans);
  return 0;
}

\(O(nk\log n\log k)\)

//知识点:DP，树状数组
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#define ll long long
#define lowbit(x) (x&-x)
const int kMaxn = 1e4 + 10;
const int kMaxk = 510;
const int kMaxv = 5010;
//=============================================================
int n, K, ans, a[kMaxn], t[kMaxk][kMaxv + kMaxv];
int maxx, maxy;
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void GetMin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
int Query(int x, int y) {
  int ret = 0;
  for (int i = x; i; i -= lowbit(i)) {
    for (int j = y; j; j -= lowbit(j)) {
      GetMax(ret, t[i][j]);
    }
  }
  return ret;
}
void Modify(int x, int y, int val) {
  for (int i = x; i <= maxx; i += lowbit(i)) {
    for (int j = y; j <= maxy; j += lowbit(j)) {
      GetMax(t[i][j], val);
    }
  }
}
//=============================================================
int main() {
  n = read(), K = read();
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    GetMax(maxy, a[i]);
  }
  maxx = K + 1, maxy += K;

  for (int i = 1; i <= n; ++ i) {
    for (int j = K; j >= 0; -- j) {
      int tmp = Query(j + 1, a[i] + j) + 1;
      GetMax(ans, tmp);
      Modify(j + 1, a[i] + j, tmp);
    }
  }
  printf("%d\n", ans);
  return 0;
}