AT_nikkei2019_qual_f Jewels 题解

设 A_x 表示容量 x 时的答案，分类讨论一下可以发现，从 A_x 转移到 A_{x+1}，最多会增加 4 个，减少 3 个。所以合并两个背包 A,B 到 B，若 C_i 的最优转移点是 A_j+B_{i-j}，那么 C_{i+1} 的最优转移点一定在 [j-4,j+4] 范围内。所以单次合并复杂度 \mathcal{O}(|A|+|B|)，所以按照哈夫曼树合并，最终复杂度 \mathcal{O}(n\log n)。

应该是对的，拍了 2000 多组。

#include<bits/stdc++.h>

#define INPUT_TYPE int
#define OUTPUT_TYPE long long

inline __attribute((always_inline)) INPUT_TYPE read(){
    register INPUT_TYPE x=0;register char c=getchar(),f=0;
    while(c<'0'||'9'<c) f=(c=='-'),c=getchar();
    while('0'<=c&&c<='9') x=x*10+(c&15),c=getchar();
    return f?-x:x;
}

void print(OUTPUT_TYPE x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10) print(x/10),x%=10;
    putchar(x|'0');
}

const long long INF=0x3f3f3f3f3f3f3f3f;

int a,b;
std::vector<long long> pol[200010],pnow;
std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,std::greater<std::pair<int,int> > > Q;

int main(){
    register int i,j,lat,c,v,now;
    int n=read();
    int m=read();
    for(i=1;i<=n;++i){
        c=read();v=read();
        pol[c].push_back(v);
    }

    for(c=1;c<=m;++c)if(pol[c].size()){
        std::sort(pol[c].begin(),pol[c].end(),[](int a,int b){return a>b;});
        for(i=1;i<pol[c].size();++i) pol[c][i]+=pol[c][i-1];
        pol[c].insert(pol[c].begin(),0);
        pol[c][1]=-INF;
        Q.push(std::make_pair((int)pol[c].size(),c));
    }

    while(Q.size()>1){
        a=Q.top().second,Q.pop();
        b=Q.top().second,Q.pop();
        pnow.clear();
        pnow.resize(pol[a].size()+pol[b].size()-1,-INF);

        lat=0;
        for(i=0;i<pnow.size();++i)if(i!=1){
            for(j=lat-4;j<=lat+4;++j){
                if(j==1||j<0||j>=pol[a].size()||i-j==1||i-j<0||i-j>=pol[b].size()) continue;
                if(pnow[i]<pol[a][j]+pol[b][i-j]){
                    pnow[i]=pol[a][j]+pol[b][i-j];
                    now=j;
                }
            }
            lat=now;
        }
        pol[a].swap(pnow);
        Q.push({pol[a].size(),a});
    }

    c=Q.top().second;
    for(i=1;i<=n;++i) print((pol[c][i]<=-INF/2)?-1:pol[c][i]),putchar('\n');

    // fprintf(stderr,"%lf",1.0*clock()/CLOCKS_PER_SEC);

    return 0;
}