Bzoj5441 [ceoi2018]cloud computing

当背包DP遇上动态的体积

Posted by yjjr's blog on September 17, 2018

标签:DP,思维

题面

Description

农夫约翰创立了一家为客户提供云端计算服务的公司,但是他还没开始购买计算机。于是他去了电脑商店,看了商店里所有的n台电脑的配置属性列表。每台电脑的属性有 CPU核心数量 ci,工作频率fi,价格vi,即这台电脑有ci个可以独立工作,不会互相干扰的CPU核心,可以同时给每个CPU核心分配不同的任务。当一个客户在约翰的公司里下订单的时候,订单里会指定特定的CPU核心数量Cj,最低工作频率Fj,并且会给出这个客户所能接受的定价Vj。

如果约翰接受了一个客户的订单,那就需要选出Cj个CPU核心专门为这个客户工作(这些CPU核心可能来自于不同的计算机),而且这Cj个CPU核心的工作频率至少为Fj。这些CPU核心一旦被选定为这个订单工作,就无法被分配给其他任何订单。约翰需要你告诉他:应该接受哪些订单同时买下哪些电脑来最大化他的利润。(利润=接受的所有订单的定价之和-购买的计算机的价格之和)

原题面

Input

第一行输入包含一个整数$n(1<=n<=2000)$,表示商店里计算机的数量。 接下来的$n$行,每行包含3个用空格隔开的整数,$ci,fi,vi(1<=ci<=50,1<=fi<=10^9,1<=vi<=10^9),$ 分别表示商店里第$i$台计算机的CPU核心数量,工作频率和价格 之后的一行包括一个整数$m,(1<=m<=2000)$,表示订单的数量。 接下来的$m$行,每行包括3个用空格隔开的整数$Cj,Fj,Vj(1<=Cj<=50,1<=Fj<=10^9,1<=Vj<=10^9),$ 表示这个订单所需的CPU核心数量,CPU核心的最低工作频率,以及这个顾客愿意给出的定价。

分组数据范围: 对于18%的数据点,n<=15 对于另外18%的数据点,m<=15 对于另外18%的数据点,n,m<=250,ci=Cj=1 对于另外18%的数据点,fi=Fj=1 对于另外18%的数据点,vi=Vj=1 对于另外10%的数据点,没有任何限制

Output

输出只有一行,包含一个整数,表示能达到的最大利润

Sample Input

4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550

Sample Output

350

样例解释

商店里有4台计算机和3份可以接受的订单。 用700和750的代价买两个有4个CPU核心的计算机,(即输入中的第1台和第4台计算机) 然后接受前2个订单获得300+1500=1800的总定价,于是,约翰就有了4个工作频率为2200的CPU核心和4个工作频率为2000的CPU核心,他只需要把这8个CPU核心中的任意1个分配给第一个订单,接着把剩余7个CPU核心中的任意6个分配给第二个订单,就满足了这2个订单的要求。最后他获得利润就是1800-(700+750)=350

题解

巧妙的思维题

把此题转化为背包问题的模型

计算机和订单视为不同的物品,计算机成本视为负,订单的需求核心数量视为负

先把这些物品按照频率从大到小排序,之后跑背包,注意是动态,实时更新背包体积的

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define ll long long
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//******head by yjjr******
const int maxn=2e3+6;
struct node{int c,f,v;}q[maxn<<1];
inline bool cmp(node a,node b){return a.f==b.f?a.v<b.v:a.f>b.f;}
int n,m,tot;ll f[maxn*50+6],ans;
int main(){
	n=read();rep(i,1,n)q[i]=(node){read(),read(),-read()};
	m=read();rep(i,1,m)q[n+i]=(node){-read(),read(),read()};
	sort(q+1,q+1+n+m,cmp);
	mem(f,-inf);f[0]=0;
	rep(i,1,n+m){
		if(q[i].c>0){
			dep(j,tot,0)f[j+q[i].c]=max(f[j+q[i].c],f[j]+q[i].v);
			tot+=q[i].c;
		}
		else rep(j,0,q[i].c+tot)f[j]=max(f[j-q[i].c]+q[i].v,f[j]);
	}
	rep(i,0,tot)ans=max(ans,f[i]);
	cout<<ans<<endl;
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr