[DP记录]AT4120 [ARC096D] Sweet Alchemy
command_block
2021-02-13 14:28:49
**题意** : 给出一棵有根树，每个节点上有无穷多个物品，购买节点 $u$ 的一个物品需要花费 $m_u$ 元。
记节点 $u$ 的物品购买了 $c_u$ 个。则需要满足 $c_{fa(u)}\leq c_u\leq c_{fa(u)}+d$ ，其中 $d$ 为给定常数。
问在有 $x$ 元的情况下最多购得多少个物品。
$n\leq 50,\ x,m_u,d\leq 10^9$ ，时限 $\texttt{2s}$。
------------
将 $c$ 数组做树上差分，记 $d_u=c_u-c_{fa(u)}$ ，则 $0\leq d_u\leq d$。
而将 $d_u$ 增加 $1$ 所需的代价是子树 $u$ 内 $m$ 的和。而受益则为子树 $u$ 的大小。
现在问题变成了 $n$ 个物品的多重背包。（注意根不受 $d$ 的限制）
$x$很大，直接 $\rm DP$ 不可行。
不难想到一种贪心，即按照性价比选择，可惜的是，这个贪心是错误的。
这个贪心能排除一些较劣的解，简化决策 : 若有两个物品 $i,j$ 满足 $\dfrac{m_i}{v_i}<\dfrac{m_j}{v_j}$ ，且 $c_i\geq v_j$ ，显然可以将 $v_j$ 个 $i$ 换成 $v_i$ 个 $j$ ，这样收益没有变化，但是代价减少了。
这告诉我们，购买某个物品个数超过 $n$ 的部分可以贪心调整。所以每个物品保留 $O(n)$ 个做背包，区其余按照性价比贪心即可。
设 $f[k]$ 为获得收益为 $k$ 时最小的成本，类似多重背包转移即可。使用二进制拆分实现，复杂度为 $O(n^4\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const ll INF=1ll<<60;
int lim;
void add(ll *f,ll m,int v){
for (int i=lim;i>=v;i--)
f[i]=min(f[i],f[i-v]+m);
}
struct Data{ll m;int v,c;}b[55];
bool cmp(const Data &A,const Data &B)
{return 1ll*A.v*B.m>1ll*B.v*A.m;}
int n,x,d,fa[55];
ll f[125500];
int main()
{
scanf("%d%d%d",&n,&x,&d);
lim=n*n*n;
scanf("%d",&b[1].m);
for (int i=2;i<=n;i++)
scanf("%lld%d",&b[i].m,&fa[i]);
for (int i=n;i;i--){
b[fa[i]].m+=b[i].m;
b[fa[i]].v+=++b[i].v;
}
for (int i=1;i<=n;i++)
b[i].c=(b[i].v==n) ? n : min(n,d);
for (int i=1;i<=lim;i++)f[i]=INF;
for (int i=1;i<=n;i++){
int t=b[i].c;
for (int j=0;(1<<j)<=t;j++){
add(f,(ll)b[i].m<<j,(ll)b[i].v<<j);
t-=(1<<j);
}if (t)add(f,(ll)b[i].m*t,(ll)b[i].v*t);
}
sort(b+1,b+n+1,cmp);
int ans=0;
for (int j=0;j<=lim;j++)
if (f[j]<=x){
int s=x-f[j],tot=j;
for (int i=1;i<=n;i++){
int c=s/b[i].m;
if (b[i].v<n)c=min(c,d-b[i].c);
tot+=c*b[i].v;s-=c*b[i].m;
}ans=max(ans,tot);
}
printf("%d",ans);
return 0;
}
```