暑假集训 Day12 总结

前言：

$539$ 拿下线下第一，很开心。

F.自助餐

这道题目有点可惜，没加排序痛失 $61$ 分。

正解思路：

一眼 dp，采用 01 背包。先排序，按照消耗时间从小到大排序，这样可以保证能枚举到每一种方案。接下来是 01 背包的模板。最后，把所有的状态枚举一遍，求最大值输出即可。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 6e3+20;
const int M = 3e3+20;
int n, t, ans = -1;
int dp[N];
struct node {
	int a, b;
} a[M];
bool cmp(node x, node y) {
	return x.a < y.a;
}
signed main() {
	freopen("free.in", "r", stdin);
	freopen("free.out", "w", stdout);
	cin >> n >> t;

	for (int i = 1; i <= n; i++) {
		cin >> a[i].a >> a[i].b;
	}

	sort(a + 1, a + 1 + n, cmp);

	for (int i = 1; i <= n; i++) {
		for (int j = t + a[i].a - 1; j >= a[i].a; j--) {
			dp[j] = max(dp[j], dp[j - a[i].a] + a[i].b);
		}
	}

	for (int i = 1; i <= 6e3; i++) {
		ans = max(ans, dp[i]);
	}

	cout << ans;
	return 0;
}