题解：AT_arc096_d [ARC096F] Sweet Alchemy

· · 题解

背包妙妙题。

首先，转换一下题意，因为原来具有依赖性，不太好处理（c_{p_i}\le c_i \le c_{p_i}+d）：考虑实际上是一棵树，设以 i 为根子树大小为 v_i，子树内所有 m_i 的和为 w_i 可以将题目转换为有 n 个物品，第 i 个物品价值为 v_i，花费为 w_i，其中，第 1 个物品可以选任意个，其他最多 d 个，求最大价值。

还是不好做，为什么呢？因为除了 n，都是 10^9 级别。那么我们就关注 n，如何做到复杂度只与 n 有关：贪心，直接 \mathcal{O}(n) 取，但是这种显然几乎很多初学者最初学背包 DP 时的初始想法显然是假的，可是它却有关键的启发性，考虑什么时候是对的：假设将物品按照性价比 \frac{v_i}{w_i} 降序排，对于 i<j，选 v_j 个物品 i，一定不优于选 v_i 个物品 j，因为此时价值相同，但是前者花费小。

有什么用呢？很大用处！根据刚刚的贪心，可以得到，最优的答案当中，对于 i<j，一定满足 c_i >d-v_j \lor c_j < v_i。证明也简单：若物品 i 还可以选至少 v_j 个，物品 j 选了至少 v_i 个，将 v_i 个物品 j 换成 v_j 个物品 i 一定不劣。

但是直接这样搞肯定不方便，反正 v_i \le n\le 50，我们不妨将限制放松些，变成 c_i >d-n \lor c_j < n。那么我们可以每个物品取出最多 n 个，做背包，剩下的直接贪心。

价值比较小，大概是 n^3 级别的，对设状态，即 f_i 表示价值为 i 时的最小体积。因为是多重背包，可以二进制优化，最后复杂度就是 \mathcal{O}(n^4\log n)。

代码如下

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int inf = 1e16 + 7;
const int N = 50 + 7;
const int M = 1e6 + 7;

int n, m, d, fa[N], w[N], v[N], id[N], c[N], ans, lim, f[N * N * N];
vector<int> G[N];
vector<pii> b;

void dfs(int x)
{
    v[x] = 1;
    for(int to : G[x])
    {
        dfs(to);
        w[x] += w[to];
        v[x] += v[to];
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> d;
    cin >> w[1]; id[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        cin >> w[i] >> fa[i];
        G[fa[i]].push_back(i);
        id[i] = i, c[i] = d;
    }
    dfs(1), c[1] = m / w[1];
    sort(id + 1, id + n + 1, [&](int x, int y){return v[x] * w[y] > v[y] * w[x];});
    for(int i = 1; i <= n; i++)
    {
        int mn = min(n, c[i]);
        lim += mn * v[i];
        for(int j = 1; j <= mn; j <<= 1)
        { 
            b.push_back({j * v[i], j * w[i]});
            mn -= j;
        }
        if(mn) b.push_back({mn * v[i], mn * w[i]});
    }
    for(int i = 1; i <= lim; i++)
        f[i] = inf;
    for(auto[V, W] : b)
        for(int i = lim; i >= V; i--)
            f[i] = min(f[i], f[i - V] + W);
    for(int i = 0; i <= lim; i++)
    {
        if(f[i] > m) continue ;
        int cur = i, re = m - f[i];
        for(int j = 1; j <= n; j++)
        {
            int tot = min(c[id[j]] - min(n, c[id[j]]), re / w[id[j]]);
            re -= tot * w[id[j]], cur += tot * v[id[j]];
        }
        ans = max(ans, cur);
    }
    cout << ans;
    return 0;
}