你说得对，但是 CF 标签就图一乐

· · 题解

声明：本题解中认为各个变量及 dp 数组属于代码片段，所以用代码块包裹且不使用 latex。

好的。首先我们应该先看题。

题意

对题意可能会出现的一个误解是：认为一次检查失败，整个过程立刻停止，然后使用贪心。手摸样例就可以发现这个错误。

正确的题意是：任意检查失败之后依然可以继续获取后面的点数和进行检查，仅仅是这一次检查不计入通过的检查总数。

然后，想想怎么做。

思路 && 算法选择

对于这种题，我们一时难以想到一个最优的分配点数的策略，无法使用贪心。

对于这种复杂的多阶段决策，一般可以考虑动态规划。

一个简单的想法是，设 dp[i][j] 为现在已经进行了前 i 个操作，将 j 个点数分配在智力（也可以是力量，但是这里以智力为例）上通过的最多测试数目。

考虑状态转移方程。

显然的，对于一次获得点数的操作，立刻分配点数一定不劣于之后分配点数。而分配点数可以分到智力或力量上，我们可以取最大值。

于是就有这个转移方程：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);
//when r[i] == 0

而当操作是一次检测时，分配了足够点数的状态通过的检测次数会加一。

方程是这个：（以智力检测为例，力量检测同理）

//cnt 是之前获得的总点数
for (int j = r[i]; j <= cnt; ++j) {
  dp[i][j] = dp[i - 1][j] + 1;
}
//when r[i] > 0

上面的做法显然是无法通过的，时间和空间都会超限，我们需要优化。

空间优化

空间的优化是平凡的。用滚动数组或降维优化可以轻易地优化到 O(m)。

注意降维优化时 r[i] == 0 的操作 j 的枚举要反向（类似于 01 背包），否则前面的转移会改掉后面转移依赖的数据，就会 WA 掉。

然后，我们就要考虑优化时间。

经典错解一则

如果你像我一样没有完全想明白状态转移方程就动手，容易忽略获得点数时也要进行状态转移，然后就会想到用树状数组优化。

但是这是错的。树状数组无法简单的维护 chechmax 操作。吉司机线段树属于山本

真正的优化

注意到 m 的数据范围很小。所以获得点数的操作数量也很少。对于这种操作，我们可以使用 O(m) 的暴力做法。

对于另外两种操作，使用差分维护即可。在获得点数的操作时，先将差分推平算出原数组，然后暴力做即可。

代码

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

int dp[5005], d[5005], n, m;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    fill(dp + 1, dp + m + 1, -1e9);

    for(int i = 1, s = 0; i <= n; ++i) {
        int x;
        cin >> x;
        if (x > 0) {
            if (x <= s) {
                ++d[x], --d[s + 1];
            }
        } else if(x < 0) {
            if (0 <= s + x) {
                ++d[0], --d[s + x + 1];
            }
        } else {
            ++s;
            dp[0] += d[0];
            for (int j = 1; j <= s; ++j) {
                d[j] += d[j - 1];
                dp[j] += d[j];
            }

            for (int j = s; j; --j) {
                dp[j] = max(dp[j], dp[j - 1]);
            }

            fill(d, d + s + 2, 0);
        }
    }

    dp[0] += d[0];
    for(int j = 1; j <= m; ++j) {
        d[j] += d[j - 1];
        dp[j] += d[j];
    }
    cout << *max_element(dp, dp + m + 1);
    return 0;
}