自动搬运

查看原文

来自洛谷，原作者为

	Yemaster **

搬运于2025-08-24 22:05:28，当前版本为作者最后更新于2019-11-12 10:50:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

MasterOJ

看到题目描述，消耗时间？价值？

不就是一个背包吗？

不过加了一个时间限制，那么本来循环从$T_i$~$MAX_T$，就改成$T_i$~$D_i$，高高兴兴地写完代码

	for (RI i = 1; i <= N; ++i) {
		scanf("%d%d%d", &T, &D, &C);
		if (D > mx)
			mx = D;
		for (RI j = D - 1; j >= T; --j) {
			if (f[j - T] + C > f[j]) {
				g[j] = g[j - T];
				g[j].push_back(i);
				f[j] = f[j - T] + C;
			}
		}
	}

太高兴了，$T,D,C$连数组都不用开了

再循环扫一遍$f$就行了

	int ans = -1;
	int mni = -1;
	for (RI i = 1; i <= mx; ++i)
		if (f[i] > ans)
			ans = f[i], mni = i;
	printf("%d\n", ans);
	printf("%d\n", g[mni].size());
	for (vector<int>::iterator it = g[mni].begin(); it < g[mni].end(); it++)
		printf("%d ", *it);

emmm，全是$WA$，只有$25$分

问题出在哪里呢？

普通的背包的限制都是$Max_T$，所有人的限制都是一样的，肯定不会越界。但是这次的限制不一样，你只是保证了当前没有超时，而不能保证前面的没有超时。

一个修正就出来了：对$D_i$从小到大排序扫。

为什么这样可以保证不会超时呢？

证明：$D_i$从小到大排序，时间限制保证了前面的比后面的低，这样后面的操作肯定会比前面的宽裕，这样就不会影响到了。。。

贴个代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define RI register int

using namespace std;

struct Node {
	int T, D, C, id;
	bool operator < (const Node& b) {
		return this->D < b.D;
	}
}a[105];

int main() {
	int N;
	scanf("%d", &N);
	int mx = -1;
	int f[2005];
	vector<int> g[2005];
	memset(f, 0, sizeof(f));
	for (RI i = 1; i <= N; ++i) {
		scanf("%d%d%d", &a[i].T, &a[i].D, &a[i].C);
		a[i].id = i;
		if (a[i].D > mx)
			mx = a[i].D;
	}
	sort(a + 1, a + N + 1);
	for (RI i = 1; i <= N; ++i) {
		for (RI j = a[i].D - 1; j >= a[i].T; --j) {
			if (f[j - a[i].T] + a[i].C > f[j]) {
				g[j] = g[j - a[i].T];
				g[j].push_back(a[i].id);
				f[j] = f[j - a[i].T] + a[i].C;
			}
		}
	}
	int ans = -1;
	int mni = -1;
	for (RI i = 1; i <= mx; ++i)
		if (f[i] > ans)
			ans = f[i], mni = i;
	printf("%d\n", ans);
	printf("%d\n", g[mni].size());
	for (vector<int>::iterator it = g[mni].begin(); it < g[mni].end(); it++)
		printf("%d ", *it);
	return 0;
}