TIOJ 2135：背包問題

TIOJ 2135：背包問題

題目大意：有 $N$ 個物品跟一個容量 $W$ 的背包，每個物品有 $w,v,c$，代表大小 $w$、價值 $v$，除了整個拿以外，也可以花 $c$ 的錢拿 $v\times\frac{w'}{w}$，有 $Q$ 次修改，每次會改某個物品的 $c$，修改完回答最大收益。

解法：發現最多只會花費一個物品的 $c$，可以分治求出不包含某個物品的 $dp$ 值，枚舉切多少後用 $\text{multiset}$ 存答案。

$\text{Code：}$

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

const int N = 1005;
const int M = 2005;

int n, m, q;
double ans[N];
vector<int> op[M];
multiset<double> ms;
int w[N], v[N], c[N], dp[M];

void divide(int l, int r) {
    if (l == r) {
        if (l == 1) ms.insert(max(dp[m], w[1] <= m ? dp[m - w[1]] + v[1] : 0));
        ans[l] = 0;
        for (int i = 1; i <= min(m, w[l]); i++) ans[l] = max(ans[l], dp[m - i] + (double) v[l] * i / w[l]);
        ms.insert(ans[l] - c[l]);
        return;
    }
    int mid = (l + r) / 2;
    for (int i = 0; i <= m; i++) op[i].emplace_back(dp[i]);
    for (int i = mid + 1; i <= r; i++) for (int j = m; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    divide(l, mid);
    for (int i = 0; i <= m; i++) dp[i] = op[i].back();
    for (int i = l; i <= mid; i++) for (int j = m; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    divide(mid + 1, r);
    for (int i = 0; i <= m; i++) dp[i] = op[i].back(), op[i].pop_back();
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        ms.clear();
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> w[i] >> v[i] >> c[i];
        fill(dp + 1, dp + m + 1, 0);
        divide(1, n);
        cout << fixed << setprecision(7) << *ms.rbegin() << '\n';
        cin >> q;
        while (q--) {
            int p, x;
            cin >> p >> x;
            ms.erase(ms.find(ans[p] - c[p]));
            c[p] = x;
            ms.insert(ans[p] - c[p]);
            cout << fixed << setprecision(7) << *ms.rbegin() << '\n';
        }
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！