正題

題目鏈接:https://www.luogu.com.cn/problem/AT4120

---

題目大意

給出$n$個(gè)物品和一個(gè)容量$m$，第$i$個(gè)物品體積為$c_i$。除了第一個(gè)物品每個(gè)物品還有一個(gè)$p_i(p_i<i)$表示如果$p_i$個(gè)物品選擇了$x$個(gè)，第$i$個(gè)物品選擇了$y$個(gè)要求滿足$x\le y\le x+d$。

$1\le n\le 50,1\le m,c_i\le 10^9,0\le d\le 10^9,1\le p<i$

---

解題思路

一個(gè)簡單的轉(zhuǎn)換，變成一棵樹之后選擇就變?yōu)榱艘淮伪仨氝x擇一個(gè)子樹。除了點(diǎn)$1$外其他最多就只能選擇$d$次。

就變成了一個(gè)多重背包，但是容量和體積很大，考慮貪心。因?yàn)閮r(jià)值都比較小，對于足夠大的情況性價(jià)比貪心是對的，所以我們可以考慮先把小的直接做背包，大的貪心選。

背包時(shí)每個(gè)物品最多選$min\{n,d\}$次，設(shè)$f_i$表示價(jià)值為$i$時(shí)的最小體積，然后枚舉一個(gè)背包權(quán)值，剩下的貪心就好了。二進(jìn)制分組或者單調(diào)隊(duì)列優(yōu)化多重背包都能過

時(shí)間復(fù)雜度$O(n^4\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=51; struct node{ll w,v,id; }a[N]; ll n,m,d,p[N],f[N*N*N],ans; bool cmp(node x,node y) {return x.v*y.w>y.v*x.w;} signed main() {scanf("%lld%lld%lld",&n,&m,&d);scanf("%lld",&a[1].w);a[1].v=1;a[1].id=1;for(ll i=2;i<=n;i++)scanf("%lld%lld",&a[i].w,&p[i]),a[i].v=1;for(ll i=n;i>1;i--)a[p[i]].w+=a[i].w,a[p[i]].v+=a[i].v,a[i].id=i;ll mx=n*n*n;memset(f,0x3f,sizeof(f));f[0]=0;for(ll i=1;i<=n;i++){ll x=min(n,d);for(ll j=1;j<=x;j<<=1){ll w=a[i].w*j,v=a[i].v*j;for(ll k=mx;k>=v;k--)f[k]=min(f[k],f[k-v]+w); x-=j;}if(!x)continue;ll w=a[i].w*x,v=a[i].v*x;for(ll k=mx;k>=v;k--)f[k]=min(f[k],f[k-v]+w);}sort(a+1,a+1+n,cmp);for(ll p=0;p<=mx;p++){if(f[p]>m)break;ll v=p,w=f[p],i=1;for(i=1;i<n;i++){if(a[i].id==1)break;ll x=min(d-min(n,d),(m-w)/a[i].w);w+=x*a[i].w;v+=x*a[i].v;}ll x=(m-w)/a[i].w;w+=x*a[i].w;v+=x*a[i].v;ans=max(ans,v); }printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的AT4120-[ARC096D]Sweet Alchemy【贪心,背包】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。