bzoj3163 Eden的新背包问题

多重背包，$q$ 次询问，每次问删一个物品之后花费 $x$ 能装多少物品

$n \leq 3000, x \leq 1000, q \leq 300000$

sol：

网上有很多假做法

正解应该是考虑分治

先二进制拆物品，然后记 $solve(l,r)$ 表示不考虑 $[l,r]$ 的操作的 dp

每次递归的时候先把 $[mid+1,r]$ 的 dp 数组搞出来，然后递归 $[l,mid]$，然后删除 $[mid+1,r]$

同样的，把 $[l,mid]$ 的 dp 数组搞出来，递归 $[mid+1,r]$ ，然后删除 $[l,mid]$

递归到 $[l,l]$ 的时候会确保只有 $[l,l]$ 区间没被算

这样每层实际上只跑了一次 dp，分治有 log 层，所以复杂度是 $O(n^2log^2n)$ （拆物品带一个 log，重量与 $n$ 同级）

单调队列可以少一个 log

#include<bits/stdc++.h>

#define LL long long

#define rep(i,s,t) for(register int i = (s),i##end = (t); i <= i##end; ++i)

#define dwn(i,s,t) for(register int i = (s),i##end = (t); i >= i##end; --i)

using namespace std;

inline int read()

{

    int x=,f=;char ch;

    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f=-f;

    for(;isdigit(ch);ch=getchar())x=*x+ch-'';

    return x*f;

}

const int maxn = ;

vector<pair<int, int> > qs[maxn];

int n, dfn, curdep;

int a[maxn], b[maxn], lb[maxn], rb[maxn];

int ans[ * maxn], dp[], fzd;

void cdq(int l, int r) {

    if(l == r) {

        rep(i, , qs[l].size() - ) ans[qs[l][i].second] = dp[qs[l][i].first];

        return;

    }

    int mid = (l + r) >> ;

    int tmp[];

    memcpy(tmp, dp, sizeof(tmp)); //fzd++;

    rep(i, lb[mid+], rb[r]) dwn(j, , a[i]) dp[j] = max(dp[j], dp[j - a[i]] + b[i]);

    cdq(l, mid);

    memcpy(dp, tmp, sizeof(dp)); //fzd++;

    rep(i, lb[l], rb[mid]) dwn(j, , a[i]) dp[j] = max(dp[j], dp[j - a[i]] + b[i]);

    cdq(mid+, r);

    memcpy(dp, tmp, sizeof(dp)); //fzd++;

}

int main()

{

    n = read();

    rep(i, , n) {

        int u = read(), v = read(), w = read(), j;

        lb[i] = dfn + ;

        for(j=;(j<<)<=(w+);j<<=)  dfn++, a[dfn] = u * j, b[dfn] = v * j;

        if(w+-j>) dfn++, a[dfn] = (w+-j) * u, b[dfn] = (w+-j) * v;

        rb[i] = dfn;

    }

    int q = read();

    rep(i, , q) {

        int x = read() + , y = read();

        qs[x].push_back(make_pair(y, i));

    }

    cdq(, n);

    rep(i, , q) printf("%d\n", ans[i]);

    //if(fzd >= 3 * n) cout << "False" << endl;

}

巴特西

bzoj3163 Eden的新背包问题

最新文章

热门文章