P11112 [ROI 2024] 机器人物流 (Day 1)

题目背景

翻译自 ROI 2024 D1T1。

在 ROI 2224 举办之时，一群能够克隆自身的机器人负责送货。人们不用出门，可以直接通过窗户拿到货物。

最开始只有一个送货机器人。在任何时候，最上面的机器人可以在自己上方克隆出一个或多个新的机器人，形成一个“机器人柱”。每个机器人的高度等于一层楼。

在送货过程中，机器人柱会沿着宿舍楼从左到右移动。机器人的数据库中包含了订单列表，每个订单都指定了一个需要送货的窗户。当机器人队列经过一个窗户时，如果队列中有机器人位于窗户所在的高度，则可以直接完成送货。

在移动过程中，机器人柱可能会碰到障碍物。碰到障碍物后，只有位于障碍物高度上方的机器人能够继续移动。这些机器人在经过障碍物后会立刻重新排成一个机器人柱，并且可以继续移动、克隆和完成送货任务。

障碍物和窗户之间的距离足够大，因此机器人在经过障碍物时不会同时经过窗户。

题目描述

每完成一个订单，机器人公司会获得 $p$ 个虚拟货币，而克隆一个新机器人的成本是 $c$ 个虚拟货币。最终利润等于订单配送的总收入减去所有机器人克隆的总成本。公司希望最大化利润。请你确定公司可以获得的最大利润。

公司不需要完成所有订单，且机器人可以在任何时候停止送货。

输入格式

第一行包含四个整数 $n,m,c,p$（$0\le n,m\le 100000$，$1\le c,p\le 1000000$），分别表示障碍物的数量、订单的数量、克隆一个机器人的成本和每个订单的配送收入。

接下来的 $n+m$ 行描述了障碍物和窗户的详细信息，按从左到右的顺序给出。每行包含两个整数 $t_i$ 和 $h_i$（$1\le t_i\le 2$，$1\le h_i\le 1000000$），其中 $t_i$ 表示对象的类型（$1$ 为障碍物，$2$ 为窗户），$h_i$ 表示障碍物的高度或窗户所在的楼层。

保证有 $n$ 个障碍物，剩余 $m$ 个为窗户。

输出格式

输出一个整数，表示可以获得的最大利润。

输入输出样例 #1

输入 #1

2 3 2 6
1 2
2 3
1 1
2 6
2 2

输出 #1

4

输入输出样例 #2

输入 #2

1 3 1 5
2 2
2 1
1 9
2 1

输出 #2

9

说明/提示

样例 $1$ 解释：

以下是订单配送的最佳策略之一，如果选择配送到第二个窗户，不会增加公司的利润。

样例 $2$ 解释：

只需要克隆一次机器人，用来配送到第一个窗户，因为这个新克隆的机器人可以继续用来配送到第二个窗户。为了配送到第三个窗户而进行额外的克隆在经济上是不划算的。

下面是各个子任务的分值和特殊性质表格。全部数据范围见输入格式。

子任务	分值	特殊性质
$1$	$24$	$n\le 100,m\le 100,h_i\le 100$
$2$	$12$	$n=0$
$3$	$14$	$n=1$
$4$	$15$	$m=1$
$5$	$17$	$c=1,p=10^6$ 且障碍物高度均为 $1$
$6$	$18$	无

C++实现

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n , m , c , p , cnt , cost[100010];//m个订单，所以开100000
int main(){
	scanf("%lld%lld%lld%lld" , &n , &m , &c , &p);
	int obstacle = 0;
	for(int i = 1 ; i <= n + m ; ++i){
		LL t , h;
		scanf("%lld%lld" , &t , &h);
		if(t == 1)//障碍物
			obstacle += h;
		else//窗户
			cost[++cnt] = h + obstacle;//代价=窗户高+之前所有障碍物的高度
	}
	for(int i = 1 ; i <= m ; ++i)
		cost[i] -= 1;//初始即有一个机器人
	sort(cost + 1 , cost + m + 1);//排序cost
	LL ans = 0;//统计答案
	for(int i = 1 ; i <= m ; ++i)
		ans = max(ans , i * p - cost[i] * c);//更新答案
	printf("%lld" , ans);
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容