「雅礼集训 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[2][K],g[2][K]; int pre,now,pos,n,k,mx; vector<ll>vec[M]; inline int rd(){int x=0;char c=getchar();bool f=0;while(!isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);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)>>1;ll num=0,point=-1;for(int i=max(mid-sum,l);i<=r&&i<mid;++i){if(g[pre][i]+vec[pos][mid-i-1]>num){num=g[pre][i]+vec[pos][mid-i-1];point=i;}}if(point<0)point=l;g[now][mid]=num;solve(l,point,L,mid-1,sum);solve(point,r,mid+1,R,sum); } int main(){n=rd();k=rd();int x,y;for(int i=1;i<=n;++i){x=rd();y=rd();vec[x].push_back(y);mx=max(mx,x);}now=1;pre=0;for(int i=1;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=1;j<x;++j)vec[i][j]+=vec[i][j-1];for(int j=0;j<i;++j){int p=0;for(int l=j;l<=k;l+=i,p++)g[pre][p]=dp[pre][l],g[now][p]=0;p--;solve(0,p,0,p,vec[i].size());for(int l=j,p=0;l<=k;l+=i,p++)dp[now][l]=max(dp[now^1][l],g[now][p]);}}for(int i=1;i<=k;++i)printf("%lld ",dp[now][i]);return 0; }

转载于:https://www.cnblogs.com/ZH-comld/p/10458164.html

总结

以上是生活随笔为你收集整理的「雅礼集训 2017 Day5」珠宝的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。