正題

題目鏈接:https://loj.ac/p/6039

---

題目大意

有$n$個(gè)物品，第$i$個(gè)費(fèi)用為$w_i$，價(jià)值為$v_i$，對于$k\in [1,m]$求費(fèi)用為$m$時(shí)能獲得的最大價(jià)值。

$1\le n\le 10^6,1\le m\le 5\times 10^4,1\le w_i\le 300,1\le v_i\le 10^9$

---

解題思路

好早以前寫的不過不知道為啥錯(cuò)了，現(xiàn)在來補(bǔ)個(gè)新的。

$w_i$很小，考慮以其為突破口，顯然地我們可以把$w_i$相同的按照$v_i$從大到小排序，那么對于每個(gè)$w_i$，我們就可以選擇若干個(gè)。

設(shè)$f_{i,j}$表示做到$w=i$時(shí)費(fèi)用為$j$的最大價(jià)值和，那么有
$$f_{i,j}=f_{i?1,j?ki}+s_{i,z}$$
（$s_{i,z}$表示$w=i$的物品中前$z$大的價(jià)值和）

這個(gè)式子很難用常規(guī)的優(yōu)化，但是可以用四邊形不等式。至于證明，我們有$w_{i,j}=s_{j?i}$
要證明
$$w_{i,j}+w_{i+1,j+1}\ge w_{i,j+1}+w_{i+1,j}$$
$$s_{j?i}+s_{j?i}\ge s_{j?i+1}+s_{j?i?1}$$
然后因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$s_{i+1}?s_i$是遞減的，所以成立。

那么我們現(xiàn)在對于每個(gè)枚舉的$w=i$，把所有的$ik+j(j\in [0,i))$都分成一組。

然后對于每一組我們都用四邊形不等式優(yōu)化，不過我忘了優(yōu)化的方法了，還是記一下吧：

對于所有的可能的決策我們用一個(gè)單調(diào)隊(duì)列記錄，順帶記錄$z_i$表示隊(duì)列里第$i$個(gè)決策和第$i+1$個(gè)決策的交叉點(diǎn)（在$z_i$之前$q_i$更優(yōu)，$z_i$以之后$q_{i+1}$更優(yōu)）。

然后每次彈出隊(duì)列前面的來找答案，加入的時(shí)候我們就二分出隊(duì)尾和新加入的決策交換點(diǎn)，然后一直彈尾部直到不交叉。

時(shí)間復(fù)雜度：$O(mw\log m)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ll long long using namespace std; const ll N=5e4+10; ll n,m,g,f[2][N],q[N],z[N]; vector<ll> w[310]; bool cmp(ll x,ll y) {return x>y;} ll calc(ll i,ll j,ll p,ll k) {return f[!g][i*p+k]+w[p][j-i-1];} ll bound(ll i,ll j,ll p,ll k){ll l=i+1,r=(m-k)/p;while(l<=r){ll mid=(l+r)>>1;if(calc(i,mid,p,k)<calc(j,mid,p,k))l=mid+1;else r=mid-1;}return l; } signed main() {freopen("jewelry.in","r",stdin);freopen("jewelry.out","w",stdout); scanf("%lld%lld",&n,&m);for(ll i=1,c,v;i<=n;i++){scanf("%lld%lld",&c,&v);w[c].push_back(v);}g=0;for(ll p=1;p<=300;p++){if(w[p].empty())continue;g^=1;memcpy(f[g],f[!g],sizeof(f[g])); // memset(f[g],0,sizeof(f[g]));sort(w[p].begin(),w[p].end(),cmp);while(w[p].size()<=m/p)w[p].push_back(0);for(ll i=1;i<w[p].size();i++)w[p][i]+=w[p][i-1];for(ll k=0;k<p;k++){ll head=1,tail=0;for(ll i=0;i*p+k<=m;i++){while(head<tail&&z[head]<=i)head++;if(head<=tail)f[g][i*p+k]=max(f[g][i*p+k],calc(q[head],i,p,k));while(head<tail&&z[tail-1]>=bound(i,q[tail],p,k))tail--;z[tail]=bound(i,q[tail],p,k);q[++tail]=i;}}}for(ll i=1;i<=m;i++)printf("%lld ",f[g][i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Loj#6039-「雅礼集训 2017 Day5」珠宝【四边形不等式,dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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