简单

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 7;
const int MAX_M = 5500; // 使用常量定义上限
long long a[N];
long long tree[510][MAX_M + 1]; // 树状数组大小，考虑到索引从1开始
long long dp[10010][510];
int n, m;

// 获取低位权值
inline long long lowbit(long long x) {
return x & (-x);
}

// 更新树状数组
void update(int L, int R, long long d) {
for (int i = L; i <= m + 1; i += lowbit(i)) {
for (int j = R; j <= MAX_M; j += lowbit(j)) {
tree[i][j] = max(d, tree[i][j]);
}
}
}

// 查询树状数组
long long Sum(int L, int R) {
long long ans = 0;
for (int i = L; i; i -= lowbit(i)) {
for (int j = R; j; j -= lowbit(j)) {
ans = max(ans, tree[i][j]);
}
}
return ans;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);

cin >> n >> m;  // 输入n和m的值
for (int i = 1; i <= n; i++) {
    cin >> a[i];  // 输入数组a
}

// 初始化dp数组
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        dp[i][j] = 0;  // 初始化dp
    }
}

// 动态规划及树状数组更新
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 0; j--) {
        dp[i][j] = Sum(j + 1, a[i] + j) + 1;  // 状态转移方程
        update(j + 1, a[i] + j, dp[i][j]);  // 更新树状数组
    }
}

// 输出最终结果
cout << Sum(m + 1, MAX_M) << endl;

return 0;

}