P6359 [CEOI2018] Cloud computing 题解

jianhe · 2023-08-14 16:49:42 · 题解

P6359 [CEOI2018] Cloud computing

算法：贪心+动态规划

• 可以将买进的电脑和订单存到同一个结构体数组里面，买进的价格用负数表示。

• 要卖出电脑，首先要买进数量 \ge 订单需求的核心数并且时钟频率 \ge 订单需求。因此，我们可以用贪心思想，把电脑按时钟频率从大到小排序，保证卖出时，之前买进的时钟频率 \ge 订单需求。

• 排序时，若时钟频率相同，买进的电脑应排在前面，不然还没买进就要卖出了，结果显然偏小。

• 排完序后，我们对每一台电脑（订单），都有两种选择：买（卖）或不买（不卖）。很明显是01 背包。用 dp_j 表示核心数为 j 时，收获的最大收益。

代码实现：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;//不开long long见祖宗 
const ll N=2e5+10;
ll n,m,ct,ans,dp[N];
struct Pc{
    ll c,f,v;
}s[N];
bool cmp(Pc l,Pc r){
    //按时钟频率从大到小排序 
    if(l.f==r.f) return l.v<r.v;
    return l.f>r.f;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i].c>>s[i].f>>s[i].v;
        s[i].v=-s[i].v;//为了区分购进的电脑和订单，电脑的价格用负数存 
    }
    cin>>m;
    for(int i=n+1;i<=n+m;i++) cin>>s[i].c>>s[i].f>>s[i].v;
    //用一个结构体存电脑和订单 
    sort(s+1,s+n+m+1,cmp);
    memset(dp,128,sizeof(dp));
    //初始化收益为无穷小，因为购进电脑时，价格为负 
    dp[0]=0;
    for(int i=1;i<=n+m;i++){
        //01背包 
        if(s[i].v<0){
            for(int j=ct;j>=0;j--)
                dp[j+s[i].c]=max(dp[j+s[i].c],dp[j]+s[i].v);
            ct+=s[i].c;//ct记录当前的核心数，确定dp的范围 
        }else{
            for(int j=0;j<=ct-s[i].c;j++)
                dp[j]=max(dp[j],dp[j+s[i].c]+s[i].v);
        }
    }
    //ans初始化为0，因为不购进任何电脑时，收益为0 
    for(int j=0;j<=ct;j++) ans=max(ans,dp[j]);
    cout<<ans;
    return 0;
}