题解 P6359 【[CEOI2018]Cloud computing】

☯☯枫☯☯ · 2021-04-23 19:50:21 · 题解

题目传送门

~~Day1 T1 就这种难度了……~~

算法分析：01背包

拿到题目真没什么思路，先简单讲一下部分分的做法。

对于 \text{Subtask 1,2}，考虑二进制枚举所有方案，然后计算利润。时间复杂度至少 \mathcal{O}(2^n) 。~~码量比正解还大，就不放了……~~
观察 \text{Subtask 3}，c_i=C_j=1，就是一台计算机恰好完成一个订单，是不是很像匹配？可以用二分图带权最大匹配或者最大流（考试时没想到怎么切这个子任务……如果有更好的方法，欢迎交流）。~~码量更大了……这分还是别切了……~~
接下来是最重要的 \text{Subtask 4}，f_i=F_i=1，那么不需要考虑时钟频率的限制。比较像01背包问题。v_i 和 V_i 很明显是价值了，那么核心数应该就对应体积。相信一般的01背包大家都会。可是，这里有两种不同的“物体”，一个是计算机，一个是订单，显然不能分两次做。怎么办呢？那就把它们合到一起。只需要把计算机的价值改为 -v_i，在计算内核数时，注意区分加上或者减去，不就可以了吗？
最后 \text{Subtask 5}，v_i=V_i=1，就是买一台计算机，然后用这台计算机尽量解决多的订单。考虑贪心，如果买了这台计算机能赚，那就买，否则不买。（由于没有写过，如有错误，请指出，谢谢！）

正解：

事实上，\text{Subtask 4} 的解法已经十分接近正解了。合并后，我们先对时钟功率进行排序，然后按照时钟功率从大到小进行决策。这样可以保证之前买的核心之后一定可以使用，就避免了原本时钟功率带来的后效性。

注意：在时钟功率相同时，应当把计算机放在前面，即“先买后卖”。~~（没买到怎么卖）~~

struct P {
    int c,f,v;
    inline void inp(int k) {//input
        c=read(),f=read(),v=k*read();
    }
    bool operator <(const P& a)const {
        if(f==a.f)return v<a.v;
        //计算机的价值为负，所以价值小的优先 
        return f>a.f;
        //时钟功率大的优先 
    }
} a[N];

用 dp_{i,j} 表示选到第 i 个“物品”，拥有 j 个核心时的情况。但是很明显会爆空间。那么我们内层倒序枚举，除去第一维第 i 个“物品”，保留 dp_j，表示拥有 j 个核心时的最大利润。 对于计算机：

dp_{j+c_i}=\max(dp_j+v_i)(j\in \left[0,cnt \right])

即：当前有 j 个核心，又买了 c_i个，花了 v_i元（v_i 是负数），到达状态 dp_{j+c_i}。

对于订单：

dp_j= \max(dp_{j+C_i}+V_i)(j \in\left[0,cnt-C_i\right])

即：当前有 j+C_i 个核心，使用 C_i 个核心接了第 i 个订单，得到了 V_i 元。

记得倒序枚举！

下面是~~喜闻乐见的~~代码：

#include<bits/stdc++.h>
#define reg register
#define F(i,a,b) for(reg int i=(a);i<=(b);i++)
inline int read();
using namespace std;
const int N=4e3+10,M=1e5+10;
int n,m,cnt;
long long dp[M],ans;
struct P {
    int c,f,v;
    inline void inp(int k) {//input
        c=read(),f=read(),v=k*read();
    }
    bool operator <(const P& a)const {
        if(f==a.f)return v<a.v;
        //计算机的价值为负，所以价值小的优先 
        return f>a.f;
        //时钟功率大的优先 
    }
} a[N];
int main() {
    n=read();
    F(i,1,n)a[i].inp(-1);
    m=read();
    F(i,n+1,n+m)a[i].inp(1);
    sort(a+1,a+n+m+1);//排序 
    memset(dp,-0x3f,sizeof(dp));//初始化为极小值 
    dp[0]=0;//边界：dp[0]=0 
    F(i,1,n+m) {
        if(a[i].v<0) {//计算机 
            for(reg int j=cnt; j>=0; j--)//倒序转移 
                dp[j+a[i].c]=max(dp[j+a[i].c],dp[j]+a[i].v);
            cnt+=a[i].c;//cnt记录当前可能最大的核心数 
        } else {//订单 
            F(j,0,cnt-a[i].c)//由于是从下标较大的状态转移过来，事实上也是倒序 
                dp[j]=max(dp[j],dp[j+a[i].c]+a[i].v);
        }
    }
    F(i,0,cnt)ans=max(ans,dp[i]);//取最大值 
    printf("%lld",ans);
    return 0;
}
inline int read() {
    reg int x=0;
    reg char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}

欢迎交流讨论，请点个赞哦~