LOJ6039 珠宝

佚名 4年前 (2020-01-17) 随笔 2197人围观抢沙发百度已收录

珠宝

有 \(N\) 个物品，每个物品有重量 \(C_i\) 和价值 \(V_i\)，每个物品可以买至多一个。对于每个 \(i ∈ [1, K]\)，求重量不超过 \(i\) 时可以得到的最大价值。

\(N ≤ 10^6，K ≤ 5 × 10^4，C_i≤ 300，V_i≤ 109\)。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解

\(n\) 很大，但是 \(C_i\) 很小，所以考虑相同的 \(C_i\) 一起处理。显然要把 \(V_i\) 从大到小排序，记排序后的前缀和为 \(s(i)\)。

容易列出朴素DP

\[ dp(c,k)=\max_{i=0}^{\lfloor k/c\rfloor}\{dp(c-1,k-ic)+s(i)\} \]

可以发现如果我们把状态按照 \(\bmod c\) 分类，那么不同的类之间的转移不相关。单独考虑某一类，假设 \(\bmod c=t\)，重新写出DP的决策点转移形式。

\[ f(i)=dp(c,ic+t),f'(i)=dp(c-1,ic+t)\\ f(i)=\max_{j=0}^i \{f'(j)+s(i-j)\} \]

对于两个决策点 \(j_1<j_2\) ，若此时 \(f'(j_1)+s(i-j_1) < f'(j_2)+s(i-j_2)\)，那么以后 \(j_1\) 也一定没有 \(j_2\) 优。这是因为 \(s(i)\) 这个函数是上凸的，增长先快后慢。所以这个DP具有决策单调性。

https://www.cnblogs.com/yqgAKIOI/p/10280696.html

int n,K,C,cnt,ID;
int pos[50002]; // edit 1
vector<int64> w[301];
int64 f[301][50001];
struct node {int l,p;}q[50001];

IN int64 calc(int p,int a){
    return f[ID-1][pos[a]]+w[ID][min((int)w[ID].size()-1,p-a-1)]; // base 0
}
IN bool better(int p,int a,int b){
    return calc(p,a)>=calc(p,b);
}
int find(int l,int r,int a,int b){
    while(l<r){
        int mid=(l+r)>>1;
        if(better(mid,a,b)) r=mid;
        else l=mid+1;
    }
    return r;
}
void solve(){
    int hd=1,tl=0;
    for(int i=1;i<=cnt;++i){
        while(hd<tl and q[hd+1].l<=i) ++hd;
        if(i>1) f[ID][pos[i]]=max(f[ID][pos[i]],calc(i,q[hd].p));
        while(hd<=tl and better(max(i+1,q[tl].l),i,q[tl].p)) --tl;
        if(hd>tl) q[++tl]=(node){i+1,i};
        else if(i<cnt and better(cnt,i,q[tl].p))
            q[tl+1]=(node){find(max(i+1,q[tl].l),cnt,i,q[tl].p),i},++tl;
    }
}
int main(){
    // freopen("jewelry6.in","r",stdin),freopen("jewelry.out","w",stdout);
    read(n),read(K);
    for(int i=1;i<=300;++i) w[i].push_back(0); // for no element
    for(int i=1;i<=n;++i){
        int c=read<int>();
        w[c].push_back(read<int>());
        C=max(C,c);
    }
    for(int i=1;i<=C;++i){
        ID=i;
        sort(w[i].begin(),w[i].end(),greater<int>());
        for(int j=1;j<(int)w[i].size();++j) w[i][j]+=w[i][j-1];
        copy(f[i-1],f[i-1]+K+1,f[i]);
        for(int j=0;j<i;++j){
            cnt=0;
            for(int k=j;k<=K;k+=i) pos[++cnt]=k;
            if(cnt) solve();
        }
    }
    for(int i=1;i<=K;++i) printf("%lld%c",f[C][i]," \n"[i==K]);
    return 0;
}