[P17089] 掷出重围题解

aeiouaoeiu · 2026-07-11 19:48:38 · 题解

考虑 w_i 互不相同，这相当于 01 背包。直接做可以得到 \Omicron(ns) 做法。

考虑整道题。沿用 01 背包的状态，尝试将上一次加入的位置加入状态，按照 w_i 从小到大决策，可以确定球 i 在到达 w_i 后额外走的路程。转移形如 f_{i - 1, j, k} + \max(k + 1, w_i)\to f_{i, j + x_i, \max(k + 1, w_i)}。

进一步观察，额外走的路程是 \Omicron(n) 的，也就是对于确定的 i, j 只有 \Omicron(n) 种 f_{i, j, k} 有值。压缩一下状态，k 表示上一次加入的位置是 w_i + k - 1，k = 0 时表示 w_\text{lst}<w_i，对一个 i 转移完成后，做 f_{i, j, k}\to f'_{i, j, \max(0, k - (w_{i + 1} - w_i))} 偏移一下即可。

时间复杂度 \Omicron(n^2s)。

:::info[code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 507, p = 998244353;
int n, s;
ll f[maxn][maxn], g[maxn];
pair<int, int> pir[maxn];
void ups(ll &a, ll b) {
    a = max(a, b);
}
int main(void) {
    //freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stout);
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        cin >> pir[i].first;
    }
    for (int i = 1; i <= n; i++) {
        cin >> pir[i].second;
    }
    sort(pir + 1, pir + 1 + n);
    for (int i = 0; i <= s; i++) {
        for (int j = 0; j <= n; j++) f[i][j] = -1e18;
    }
    f[0][0] = 0;
    pir[n + 1].first = pir[n].first;
    for (int i = 1, d; i <= n; i++) {
        for (int j = s; j >= pir[i].second; j--) {
            for (int k = 0; k <= n; k++) {
                ups(f[j][k + 1], f[j - pir[i].second][k] + pir[i].first + k);
            }
        }
        for (int j = 0; j <= s; j++) {
            d = pir[i + 1].first - pir[i].first;
            for (int k = 0; k <= n; k++) {
                g[k] = -1e18;
                ups(g[max(0, k - d)], f[j][k]);
            }
            for (int k = 0; k <= n; k++) {
                f[j][k] = g[k];
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i <= s; i++) {
        for (int j = 0; j <= n; j++) ups(ans, f[i][j]);
    }
    cout << ans << "\n";

    return 0;
}

:::

[P17089] 掷出重围 题解

[P17089] 掷出重围题解