Jewel Thief ICPC 2016 NAIPC

[ICPC 2016 NAIPC] Jewel Thief

逆天背包。

题目链接： [ICPC 2016 NAIPC] Jewel Thief 。

题目描述：

给 $n$ 个物品，每个物品有价值 $v_i$ 和重量 $w_i$ ，你需要对于每一个 $1\le i \le k$ ，求出大小为 $i$ 的背包的最大价值。

• $1\le n\le 10^6$ 。
• $1\le k \le 10^5$ 。
• $1\le v_i\le 10^9$ 。
• $1\le w_i\le 300$ 。

一个普通的背包 DP ，但是直接背包复杂度 $\mathcal{O}(nk)$ ，过不了。

考虑从 $w_i\le 300$ 入手。不妨把所有的相同重量的物品经行分组，同组内的按权值从大到小排序后累加的前缀和数组为 $a_{i,j}$ ，共有 $sz_i$ 物品。

那么写出 DP 式子（不妨设这一轮 DP 结果 $f_i$ ，上一轮 $g_i$ ，这是第 $t$ 轮）。

$$f_i=\max_{0\le j\le sz_t}\{g_{i-j\times t}+a_{t,j}\}$$

这个式子可以看作是一个类多重背包，于是考虑使用多重背包的分组优化方法。

具体的，将所有的下标按 $\bmod t$ 分组。设同组内的两个数为 $i,j$ ，那么此时很显然背包的最优转移应该是同组内之间进行转移。

写出转移式子：

$$f_i=\max_{\substack{{0\le j \le i}\\{j\bmod t=i\bmod t}}}\{g_j+a_{t,\frac{i-j}{t}}\}$$

注意到 $\frac{i-j}{t}$ 总是整数，所以我们得出结论： $a$ 具有凸性（或者凹性，反正差不多），同时注意到求解 $f$ 的式子实际上是一个 max-plus 卷积。由某一个定理得， $f_i$ 的转移具有决策单调性。所以对着优化就行。

时间复杂度 $\mathcal{O}(k\max_w\log k+n\log n)$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2000010;
using ll=long long;
int n,k,v[N],w[N],p[N];
vector<ll>a[301];
ll f[N],g[N];
int id(int i,int x,int mod){return (i-1)*mod+x;}
void upd(int j,int i,int x,int mod){
    int I=id(i,x,mod),J=id(j,x,mod),m=a[mod].size()-1;
    ll t=g[J]+a[mod][min(i-j,m)];
    if(t>f[I])f[I]=t,p[I]=j;
}
void cdq(int l,int r,int x,int mod){
    if(l+1>=r)return upd(r,r,x,mod);
    int mid=(l+r)>>1;
    int L=id(l,x,mod),R=id(r,x,mod);
    for(int i=p[L];i<=p[R];i++)upd(i,mid,x,mod);
    cdq(l,mid,x,mod);
    for(int i=l+1;i<=mid;i++)upd(i,r,x,mod);
    cdq(mid,r,x,mod);
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=300;i++)a[i].push_back(0);
    for(int i=1;i<=n;i++)scanf("%d%d",w+i,v+i),a[w[i]].push_back(v[i]);
    for(int i=1;i<=300;i++){
        int m=a[i].size()-1;
        sort(a[i].begin()+1,a[i].end(),greater<ll>());
        for(int j=1;j<=m;j++)a[i][j]+=a[i][j-1];
    }
    for(int i=1;i<=300;i++){
        for(int j=0;j<=k;j++)g[j]=f[j],f[j]=0,p[j]=1;
        for(int j=0;j<i;j++){
            int X=j,MOD=i;
            int M=(k-j)/i+1;
            if(M<=0)break;
            upd(1,1,X,MOD);
            upd(1,M,X,MOD);
            cdq(1,M,X,MOD);
        }
    }
    for(int i=1;i<=k;i++)printf("%lld ",f[i]);
    return 0;
}