ARC096F Sweet Alchemy 题解

作者: xht37 分类: 题解 发布时间: 2020-04-30 17:53

点击数:86

ARC096F Sweet Alchemy

题意

  • 有 $n$ 个物品,买一个第 $i$ 个物品需要花费 $m_i$ 元。
  • 除了第一个物品外,第 $i$ 个物品有一个上级物品 $p_i(< i)$。
  • 给定 $d$,设第 $i$ 个物品买了 $c_i$ 个,要求对于 $i(\in [2,n])$ 满足 $c_{p_i} \le c_i \le c_{p_i} + d$。
  • 一共有 $x$ 元,问最多能买多少个物品。
  • $n \le 50$,$x,d,m_i \le 10^9$。

题解

设 $v_i$ 表示 $i$ 的子树大小,$w_i$ 表示 $i$ 的子树内权值和,则原问题等价于:

有 $n$ 个物品和一个体积为 $x$ 的背包。

第 $i$ 个物品体积为 $w_i$ 价值为 $v_i$ 个数为 $c_i$。

求背包能装下的最大价值和。

$v_i \le n \le 50$,$x,c_i,w_i \le 10^9$。

这是一个经典的多重背包问题,但这里的背包体积和总价值都非常大,因此无论是以体积为状态还是以价值为状态的多重背包都行不通。

注意到物品个数和价值都很小,考虑从这个角度入手。

考虑 $i,j$ 满足 $\frac {w_i}{v_i} \le \frac {w_j}{v_j}$:

  • 若 $i$ 拿了 $v_j$ 个,体积为 $w_iv_j$,价值为 $v_iv_j$。
  • 若 $j$ 拿了 $v_i$ 个,体积为 $w_jv_i$,价值为 $v_iv_j$。

由于价值一样,但前者的体积更小,所以前者一定不劣。

因此按照 $\frac wv$ 从小到大排序后,我们可以每个物品拿 $n$ 个出来,剩下的一定是从前往后贪心的拿。

此时总价值不超过 $\mathcal O(n^3)$,于是再考虑以总价值为状态的多重背包,即设 $f_{i,j}$ 为考虑到第 $i$ 个物品,总价值为 $j$ 的最小体积。

单调队列优化是 $\mathcal O(n^4)$ 的,二进制拆分则是 $\mathcal O(n^4 \log n)$ 的,都可以接受,但后者更好写。

代码

const int N = 57;
int n, p[N], t;
vi e[N];
ll x, d, w[N], v[N], c[N];

void dfs(int x) {
    v[x] = 1;
    for (int y : e[x])
        dfs(y), v[x] += v[y], w[x] += w[y];
}

const ll inf = 1e18;
ll W[N<<3|1], V[N<<3|1], f[N*N*N], s, ans;

int main() {
    rd(n), rd(x, d, w[1]), p[1] = 1;
    for (int i = 2, f; i <= n; i++)
        rd(w[i]), rd(f), e[f].pb(i), p[i] = i, c[i] = d;
    dfs(1), c[1] = x / w[1] * v[1];
    sort(p + 1, p + n + 1, [&](int i, int j) {
        return w[i] * v[j] < w[j] * v[i];
    });
    for (int i = 1; i <= n; i++) {
        int p = ::p[i];
        ll c = min(::c[p], (ll)n);
        s += c * v[p];
        ll k = 0, x = 0;
        while (x + (1 << k) <= c)
            x += 1 << k, V[++t] = (1 << k) * v[p], W[t] = (1 << k) * w[p], ++k;
        if (c - x) V[++t] = (c - x) * v[p], W[t] = (c - x) * w[p];
    }
    for (int i = 1; i <= s; i++) f[i] = inf;
    for (int i = 1, k = 0; i <= t; k += V[i++])
        for (int j = k; ~j; j--)
            f[j+V[i]] = min(f[j+V[i]], f[j] + W[i]);
    for (int i = 0; i <= s; i++)
        if (f[i] <= x) {
            ll now = i, sum = f[i];
            for (int j = 1; j <= n; j++) {
                int p = ::p[j];
                ll c = min(::c[p] - min(::c[p], (ll)n), (x - sum) / w[p]);
                now += c * v[p], sum += c * w[p];
            }
            ans = max(ans, now);
        }
    print(ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注