CF601E A Museum Robbery

题目描述

有n个房间，每个房间有若干物品，每个物品有价值v_i和重量w_i。你可以从每个房间最多拿一个物品，背包容量为W，求最大总价值。

题解思路

采用线段树分治优化01背包。将物品按重量排序，构建线段树，每个节点存储区间内物品。通过线段树分治处理物品，合并子树DP状态，优化时间复杂度。

代码实现

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

typedef long long ll;
const ll INF = 1e18;

struct Item {
    int w, v;
    bool operator<(const Item& other) const {
        return w < other.w;
    }
};

int n, W;
vector<Item> items;
vector<vector<Item>> tree;
vector<ll> dp;

// 合并两个DP数组，保留价值递增的关键节点
vector<ll> merge(const vector<ll>& a, const vector<ll>& b) {
    int m = a.size(), k = b.size();
    vector<ll> res;
    ll max_val = -INF;
    for (int i = 0; i < m; ++i) {
        if (a[i] <= max_val) continue;
        for (int j = 0; j < k; ++j) {
            if (i + j >= W) continue;
            if (a[i] + b[j] > max_val) {
                res.push_back(a[i] + b[j]);
                max_val = a[i] + b[j];
            } else break; // 因b[j]递增，后续j+1会更小
        }
    }
    return res;
}

// 构建线段树，每个节点存储区间内物品
void build(int node, int l, int r) {
    if (l == r) {
        tree[node] = {items[l]};
        return;
    }
    int mid = (l + r) / 2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    // 合并左右子树物品
    tree[node].resize(tree[2*node].size() + tree[2*node+1].size());
    merge(items, tree[2*node], tree[2*node+1]); // 实际为合并物品列表
}

// DP处理函数，处理线段树节点并回溯
void solve(int node, int l, int r) {
    vector<ll> prev = dp;
    // 处理当前节点物品
    for (auto& item : tree[node]) {
        for (int j = W; j >= item.w; --j) {
            if (dp[j - item.w] != -INF) {
                dp[j] = max(dp[j], dp[j - item.w] + item.v);
            }
        }
    }
    if (l == r) return;
    int mid = (l + r) / 2;
    solve(2*node, l, mid);
    solve(2*node+1, mid+1, r);
    // 回溯恢复DP状态
    dp = prev;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> W;
    items.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> items[i].w >> items[i].v;
    }
    // 按重量排序并过滤
    sort(items.begin(), items.end());
    vector<Item> filtered;
    for (auto& item : items) {
        if (item.w <= W) filtered.push_back(item);
    }
    items = filtered;
    n = items.size();
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    // 初始化线段树和DP
    int size = 1;
    while (size < n) size <<= 1;
    tree.resize(4 * n);
    build(1, 0, n-1);
    dp.assign(W + 1, -INF);
    dp[0] = 0;
    // 处理线段树
    solve(1, 0, n-1);
    // 求最大价值
    ll ans = 0;
    for (int j = 0; j <= W; ++j) {
        ans = max(ans, dp[j]);
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(n log n log W)，其中n为物品数，W为背包容量
• 空间复杂度：O(n log n + log W)，主要用于线段树和DP数组

核心思想

通过线段树分治将物品分组处理，每个节点处理区间内物品，避免普通01背包的重复计算。合并子树时保留价值递增的关键重量点，优化DP数组大小，实现高效求解。

C139 线段树分治+01背包 CF601E A Museum Robbery