[loj6039]「雅礼集训 2017 Day5」珠宝 dp+决策单调性+分治

https://loj.ac/problem/6039

 

我们设dp[i][j]表示考虑所有价值小于等于i的物品，带了j块钱的最大吸引力。

对于ci相同的物品，我们一定是从大到小选k个物品，又发现最大的k个的价值在k变大的时候增长率是单调减的。

同时对于同样的ci，被转移和转移到的状态mod ci同余。

这些dp值也具有单调性，因此这个dp具有决策单调性。

我们用分治优化转移。负责度O(c*k*logk)

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define maxn 305
#define maxk 50005
#define ll long long
using namespace std;
inline int read() {
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
ll n,k,sz[maxn],pre=0,now=1;
ll dp[2][maxk],g[2][maxk];
vector<ll> q[maxn];
bool cmp(ll a,ll b) {return a>b;}
void solve(int l,int r,int ql,int qr,int x,int SZ) {
    if(l>r||ql>qr) return;
    int mid=ql+qr>>1,minmid=-1;ll val=0;
    for(int i=max(l,mid-SZ);i<mid&&i<=r;i++) {
        if(minmid==-1||g[0][i]+q[x][mid-i-1]>val) {
            val=g[0][i]+q[x][mid-i-1];minmid=i;
        }
    }
    g[1][mid]=val;
//    if(minmid==-1) minmid=l;
    solve(l,minmid,ql,mid-1,x,SZ);solve(minmid,r,mid+1,qr,x,SZ);
}
int main() {
    n=read(),k=read();
    for(int i=1;i<=n;i++) {
        int x=read(),y=read();
        q[x].push_back(y);sz[x]++;
    }
    for(int i=1;i<=300;i++) {
        if(!sz[i]) continue;
        sort(q[i].begin(),q[i].end(),cmp);
        for(int j=1;j<sz[i];j++) q[i][j]+=q[i][j-1];
        for(int j=0;j<i;j++) {
            int p=j,bk=0;
            for(;p<=k;p+=i,bk++) g[0][bk]=dp[pre][p];
            solve(0,bk-1,0,bk-1,i,sz[i]);
            p=j,bk=0;
            for(;p<=k;p+=i,bk++) dp[now][p]=max(g[0][bk],g[1][bk]);
        }
        swap(now,pre);
    }
    for(int i=1;i<=k;i++) printf("%lld ",dp[pre][i]);
}