↓Skip to main content
  1. Posts/

CodeForces-2025D Attribute Checks

·2 mins·
Table of Contents

CodeForces-2025D Attribute Checks #

Solution 1 #

遇到一个 $0$ 时, 考虑从上一个 $0$ 到现在的拿到的所有分, 因此维护 $dp[i][j]$ , 表示到在这个 $0$ 之前遇到了 $i$ 个 $0$, 并分配了 $j$ 分到 $x$ 上的最大得分. 状态转移方程为: $$ dp[i][j] = \max (dp[i - 1][j], dp[i - 1][j - 1]) + cnt[j][0] + cnt[t - j][1] $$ 其中 $cnt[k][0]$ 表示两个 $0$ 之间的不超过 $k$ 的正数个数, $cnt[k][1]$ 表示两个 $0$ 之间的不小于 $-k$ 的负数个数.

实现时可以把 $dp$ 压缩成一维.

代码如下:

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> f(m + 1, 0);
    vector<vector<int> > cnt(m + 1, vector<int>(2, 0));
    int t = 0;
    vector<int> r(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }
    for (int i = 0; i <= n; ++i) {
        if (r[i] < 0) {
            cnt[-r[i]][0]++;
        } else if (r[i] > 0) {
            cnt[r[i]][1]++;
        }
        else {
            for (int j = 2; j <= t; ++j) {
                cnt[j][0] += cnt[j - 1][0];
                cnt[j][1] += cnt[j - 1][1];
            }
            for (int j = t; j > 0; --j) {
                f[j] = max(f[j], f[j - 1]) + cnt[j][0] + cnt[t - j][1];
            }
            f[0] += cnt[t][1];
            t++;
            for (int j = 1; j <= m; ++j) {
                cnt[j][0] = 0;
                cnt[j][1] = 0;
            }
        }

    }
    cout << *max_element(f.begin(), f.end()) << endl;
    return 0;
}
↑