题解：P5391 [Cnoi2019] 青染之心

rsy_ · 2025-02-05 15:32:41 · 题解

题解区的做法都太困难的，我这种刚学 OI 的萌新肯定是不会做的。

显然按照完全背包的方式可以直接做 insert 只需要用 N 去修改 dp 值就可以了，这样可以得到比暴力高一点的分。

考虑什么 N 是有用的，发现更新了 dp 数组的 N 才有用，所以考虑记一个 f_i 表示 i 对于有没有更新 dp 数组，如果更新了再重新算，最坏复杂度 \mathcal O(Q^2W)，空间是线性的，跑出来也极快，狂暴吊打题解区所有做法 （建议把空间开成 1MB）。

#include <bits/stdc++.h>
#define lb(x) (x&-x)
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)

using namespace std;
using i64 = long long;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x, int c) {x = min(x, c);}
void chmax(int &x, int c) {x = max(x, c);}

const int maxn = 2e4 + 10, mod = 998244353;
short Q, M, N;
short v[maxn], w[maxn];
int dp[maxn]; bool f[maxn];
void calc () {
    for (int i = 1; i <= M; i ++ ) {
        dp[i] = 0;
    }
    for (int i = 1; i <= N; i ++ ) {
        f[i] = 0;
        for (int j = v[i]; j <= M; j ++ ) {
            if (dp[j - v[i]] + w[i] > dp[j]) {
                f[i] = 1; dp[j] = dp[j - v[i]] + w[i];
            }
        }
    }
}

void solve() {
    cin >> Q >> M;
    for (int i = 1; i <= Q; i ++ ) {
        string opt;
        cin >> opt; int x, y;
        if (opt == "erase") {
            N -- ;
            if (f[N + 1]) calc();
        } else {
            cin >> x >> y; N ++ ;
            v[N] = x; w[N] = y; f[N] = 0;
            for (int j = v[N]; j <= M; j ++ ) {
                if (dp[j - v[N]] + w[N] > dp[j]) {
                    dp[j] = dp[j - v[N]] + w[N]; f[N] = 1;
                }
            }
        }
        cout << dp[M] << '\n';
    }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;
  while (T--)solve();
  return 0;
}