自动搬运

查看原文

来自洛谷，原作者为

	☯☯枫☯☯ Why son code is not called daughter code?

搬运于2025-08-24 22:20:02，当前版本为作者最后更新于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;
}

AC

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