ARC096F Sweet Alchemy 题解
Visits: 301
题意
- 有 $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;
}