P16160 [ICPC 2016 NAIPC] Jewel Thief

· · 题解

首先直接 0/1 背包是 O(nk) 的。

但是 0/1 背包还有另一种写法，即将 w 相同的归为一组，取同组 v 最大的 k 个转移，记 s_i=\sum_{j=1}^{i}s_j，写成 f_{i}=\max\{f_{i-kw}+s_k\}。

然后就是 P1776 经典转化，发现 f 只能在 w 的同余层中转移，因此我们枚举余数 r，有转移 f_{iw+r}=\max\{g_{jw+r}+s_{i-j}\}。

难以优化，想了很久想试试是不是有决策单调性，于是挂了个拍看看是不是对的。跑了大概十万组后好像猜到决策是单调不降的，然后试着推了推。

设 w(j,i)=g_{jw+r}+s_{i-j}，显然有

\Delta_iw(j,i)=w(j,i+1)-w(j,i)=v_{i+1-j} \Delta_j(\Delta_iw(j,i))=\Delta_iw(j+1,i)-\Delta_iw(j,i)=v_{i-j}-v_{i+1-j}\ge 0

此时 w 的二阶混合差分非负，因此 w 满足四边形不等式，故 f_{iw+r}=\max\{g_{jw+r}+s_{i-j}\} 具有决策单调性。

非同层转移，分治或者是简化 LARSCH 算法优化做到 O(k\sum\log\frac{k}{w})，不过实际比这个小得多。

这里的代码是分治的。

::::success[代码]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int R=305,N=1e6+5,M=1e5+5;
ll s[N],f[M],g[M];vector<int>Q[R];
void solve(int w,int d,int l,int r,int L,int R)
{
    int opt=L,i=(l+r)>>1;
    for(int j=L;j<=min(R,i);j++)
    {
        if(i-j>Q[w].size())continue;
        if(f[i*w+d]<=g[j*w+d]+s[i-j])
        {
            f[i*w+d]=g[j*w+d]+s[i-j];
            opt=j;
        }
    }
    if(l<i)solve(w,d,l,i-1,L,opt);
    if(r>i)solve(w,d,i+1,r,opt,R);
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        int w,v;
        scanf("%d%d",&w,&v);
        Q[w].emplace_back(v);
    }
    for(int w=1;w<=min(k,300);w++)
    {
        if(Q[w].empty())continue;
        sort(begin(Q[w]),end(Q[w]),greater<ll>());
        for(int i=1;i<=Q[w].size();i++)s[i]=s[i-1]+Q[w][i-1];
        for(int r=0;r<w;r++)solve(w,r,0,(k-r)/w,0,(k-r)/w);
        memcpy(g,f,sizeof(f));
    }
    for(int i=1;i<=k;i++)printf("%lld ",f[i]);
    return 0;
}

::::