「雅礼集训 2017 Day5」珠宝

题目描述

Miranda 准备去市里最有名的珠宝展览会，展览会有可以购买珠宝，但可惜的是只能现金支付，Miranda 十分纠结究竟要带多少的现金，假如现金带多了，就会比较危险，假如带少了，看到想买的右买不到。展览中总共有 N 种珠宝，每种珠宝都只有一个，对于第 i种珠宝，它的售价为 Ci​ 万元，对 Miranda 的吸引力为 Vi​。Miranda 总共可以从银行中取出 K 万元，现在她想知道，假如她最终带了 i 万元去展览会，她能买到的珠宝对她的吸引力最大可以是多少？

题解

菜死了菜死了。。

因为普通的01背包问题是NP的，所以我们要观察题目中的一些特殊性质。

注意到C非常小，可以把C拿出来做文章。

对于每一个物品体积，我们可以有方程：dp[i]+sum[j-i]->dp[j]

对于C一样的物品，我们要选肯定是要先选价值大的，所以sum数组是一个上凸的。

我们可以对于每个C，再去枚举余数，在相同余数下进行dp。

因为有了上面的结论，那么我们的dp就有了单调性，若i转移到了x，那么(l-x)只会被(L-i)转移，(x-r)只会被(i-R)转移。

可以用分治dp做。

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

#define M 302

#define K 50002

#define N 1000002

using namespace std;

typedef long long ll;

ll dp[][K],g[][K];

int pre,now,pos,n,k,mx;

vector<ll>vec[M];

inline int rd(){

    int x=;char c=getchar();bool f=;

    while(!isdigit(c)){if(c=='-')f=;c=getchar();}

    while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}

    return f?-x:x;

}

inline ll cmp(ll x,ll y){return x>y;}

void solve(int l,int r,int L,int R,int sum){

    if(L>R||l>r)return;

    int mid=(L+R)>>;ll num=,point=-;

    for(int i=max(mid-sum,l);i<=r&&i<mid;++i){

        if(g[pre][i]+vec[pos][mid-i-]>num){

            num=g[pre][i]+vec[pos][mid-i-];point=i;

        }

    }

    if(point<)point=l;

    g[now][mid]=num;

    solve(l,point,L,mid-,sum);solve(point,r,mid+,R,sum);

}

int main(){

    n=rd();k=rd();int x,y;

    for(int i=;i<=n;++i){

        x=rd();y=rd();

        vec[x].push_back(y);mx=max(mx,x);

    }

    now=;pre=;

    for(int i=;i<=mx;++i)if(vec[i].size()){

        pos=i;swap(now,pre);

        sort(vec[i].begin(),vec[i].end(),cmp);int x=vec[i].size();

        for(int j=;j<x;++j)vec[i][j]+=vec[i][j-];

        for(int j=;j<i;++j){

            int p=;

            for(int l=j;l<=k;l+=i,p++)g[pre][p]=dp[pre][l],g[now][p]=;p--;

            solve(,p,,p,vec[i].size());

            for(int l=j,p=;l<=k;l+=i,p++)dp[now][l]=max(dp[now^][l],g[now][p]);

        }

    }

    for(int i=;i<=k;++i)printf("%lld ",dp[now][i]);

    return ;

}