P6359 [CEOI2018]Cloud computing 题解

Link

P6359 [CEOI2018]Cloud computing

Solve

这道题初看又是核心，又是电脑的很复杂，但是观察发现对于一同一台个电脑，核心频率都是一样的，对于一个任务，需要的核心的频率也是一样的

就想到把任务和电脑混在一起，按核心频率排序后处理。

每一个电脑或一个任务都可以考虑选或不选，于是就变成一个背包问题了，把电脑和任务都看成一个物品，频率是物品的大小，钱是物品的价值，(tot)是背包大小

如果是电脑，选的话要给别人钱，所以价值为(-V[i])

如果是物品，要占核心，相对于电脑是反的，所以大小为(-C[i])(这句话没理解也没关系，看下面的代码就知道，负负得正嘛~)

对于背包大小，如果加进来一个电脑，就相当于多了几个核心，(tot)要加上(C[i])

处理前先按核心从大到小排序，就可以保证每次坐任务的时候前面的任何一个核心都可以做

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005,maxm=2000005;
typedef long long LL;
int N,M,tot;
struct AS{
	int c,f,v;
	bool operator <(const AS B)const {return f>B.f||(f==B.f&&v<B.v);}
}a[maxn<<1];
LL F[maxm],ans;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
int main(){
	freopen("cloud.in","r",stdin);
	freopen("cloud.out","w",stdout);
	N=read();for(int i=1;i<=N;i++)a[i].c=read(),a[i].f=read(),a[i].v=-read();
	M=read();for(int i=1;i<=M;i++)a[i+N].c=-read(),a[i+N].f=read(),a[i+N].v=read();
	sort(a+1,a+1+N+M);
	memset(F,128,sizeof F);F[0]=0;
	for(int i=1;i<=N+M;i++){
		if(a[i].c>0){//电脑 
			for(int j=tot;j>=0;j--)
				F[j+a[i].c]=max(F[j+a[i].c],F[j]+a[i].v);
				tot+=a[i].c;
		}
		else {//任务 
			for(int j=0;j<=tot+a[i].c;j++)
				F[j]=max(F[j],F[j-a[i].c]+a[i].v);
		}
	}
	for(int i=0;i<=tot;i++)ans=max(ans,F[i]);
	printf("%lld
",ans);
	return 0;
}