题解：CF601E A Museum Robbery

· · 题解

动态时间区间背包问题题解

写在前面

一道很好的模板题，主要是想到构建时间轴，前面有大概思路，不过细节都在代码里了。

问题描述

给定一个初始物品列表和包含三种操作的指令序列：

  1. 添加物品（重量w, 价值v）
  2. 删除指定物品
  3. 查询当前背包最优解（哈希值输出）

要求处理这些操作并正确响应每个查询。

算法思路

采用时间轴线段树结合分层背包DP的解决方案：我们离线记录时间，然后把该时间存在的物品挂在区间内。那么不难想到，叶子结点就是统计答案的时候。

核心思想

  1. ​时间离散化：将每个操作转化为时间区间上的事件
  2. ​线段树分治：物品按生效时间区间存入线段树节点

  3. ​DP持久化：递归处理线段树时传递DP状态

    可以结合代码参考一下细节部分

    完整代码

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

const int N = 1e5 + 10; const ll base = 1e7 + 19; const ll mod = 1e9 + 7;

struct Item { int st, ed; // 生效起止时间 int vol, val; // 体积和价值 }; vector<Item> items; // 所有物品记录 int n, q, max_vol, time_cnt = 1; // 当前时间点初始化

struct SegNode { int l, r; vector<Item> items; // 本节点时间区间内的物品 } tree[N << 2];

// 建树 void build(int p, int l, int r) { tree[p] = {l, r, {}}; if (l == r) return; int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); }

// 将物品插入对应时间区间 void update(int p, int l, int r, const Item& item) { if (tree[p].l >= l && tree[p].r <= r) { tree[p].items.push_back(item); return; } int mid = (tree[p].l + tree[p].r) >> 1; if (l <= mid) update(p << 1, l, r, item); if (r > mid) update(p << 1 | 1, l, r, item); }

// 分治处理背包DP void solve(int p, vector<ll>& dp) { auto new_dp = dp; // 复制当前DP状态

// 用本节点物品更新背包
for (auto& item : tree[p].items)
    for (int j = max_vol; j >= item.vol; j--)
        new_dp[j] = max(new_dp[j], new_dp[j - item.vol] + item.val);

// 到达查询时间点
if (tree[p].l == tree[p].r) {
    ll hash = 0;
    for (int j = max_vol; j >= 1; j--)
        hash = (hash * base + new_dp[j]) % mod;
    cout << hash << "\n";
} else {
    solve(p << 1, new_dp); // 处理左子树
    solve(p << 1 | 1, new_dp); // 处理右子树
}

}

int main() { ios::sync_with_stdio(0), cin.tie(0);

// 初始物品输入
cin >> n >> max_vol;
for (int i = 0; i < n; i++) {
    int v, w; cin >> w >> v;
    items.push_back({1, -1, v, w}); // -1表示永久生效
}

// 处理操作序列
cin >> q;
while (q--) {
    int op; cin >> op;
    if (op == 1) { // 添加物品
        int v, w; cin >> w >> v;
        items.push_back({time_cnt, -1, v, w});
    } else if (op == 2) { // 删除物品
        int x; cin >> x;
        items[x - 1].ed = time_cnt - 1; // 设置结束时间
    } else { // 时间推进
        time_cnt++;
    }
}

// 构建时间线段树
build(1, 1, time_cnt);

// 将物品插入对应时间区间
for (auto& item : items) {
    if (item.ed == -1) item.ed = time_cnt;
    if (item.st <= item.ed) 
        update(1, item.st, item.ed, item);
}

// 初始化DP数组并求解
vector<ll> dp(max_vol + 1, 0);
solve(1, dp);

return 0;

}