自动搬运

查看原文

来自洛谷，原作者为

	蒟蒻·巨弱 蒻到不行啦，退役退役

搬运于2025-08-24 21:53:28，当前版本为作者最后更新于2020-11-03 13:26:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道可能只有黄题难度的紫题

这题应该是完全背包的模板题，这题用爆搜也能骗到分（懒，没打，不会打），好了，言归正传，这题其实只要处理一下每个门关闭的真实时间，因为如果前面的门关了，你就走不出去了，只要一个循环就能处理好：

for (i = 1; i < n; i++) close[i] = min (close[i], close[i-1]);

注意，门的编号从 $0$ 开始，所以我从第一扇开始处理到最后一扇就行，这应该是最难想的一个坑了

后面输入完之后直接套模板！具体解释看程序~

#include <bits/stdc++.h>
using namespace std;
#define N 1005
int n, m, i, j, k, close[N], f[N];//close数组记录门关闭的（真正的）时间，f数组是当前时间拿的最大价值 
struct baoshi{//习惯用结构体了。。。 
	int room, val, t;//宝石的 房间编号 价值 拿走的时间 
}d[N];
int main(){
	scanf ("%d%d", &n, &m);
	for (i = 0; i < n; i++) scanf ("%d", &close[i]);//0号房开始 
	for (i = 1; i < n; i++) close[i] = min (close[i], close[i-1]);
	//因为前面的门如果关上了，就不能去后面的门了，所以每扇门真正的关闭时间是前面的门最早的关闭时间 
	for (i = 1; i <= m; i++) scanf ("%d%d%d", &d[i].room, &d[i].val, &d[i].t);
	for (i = 1; i < close[0]; i++){//第一重循环，枚举时间（一定要在0号房关闭之前出去） 
		f[i] = f[i-1];//如果不偷宝石 
		for (j = 1; j <= m; j++){//枚举宝石
			if (close[d[j].room] > i /*关闭的时间大于枚举的时间，能进*/ && d[j].t <= i)//能拿 
			f[i] = max (f[i], f[i-d[j].t] + d[j].val);//拿或者不拿的最大值 
		}
	}
	printf ("%d", f[close[0]-1]);//可以理解为门关闭前最后一秒拿的价值 
	return 0;//完美收场
}

希望能帮上忙~