[AtCoder] [經典競程 90 題] 011 - Gravy Jobs（★6）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_k
題目大意:
現在有 $N$ 個工作可以做，第 $i$ 個工作要在 $D_i$ 前做完，並且要花費 $C_i$ 天，如果有做完的話可以獲得 $S_i$ 元的報酬。一天只能做一個工作，且一個工作做了就不能中途換其他工作。問最多可以得到多少報酬。

---

假設最佳解是做了 $p_1$, $p_2$, $\cdots$, $p_m$ 這些工作，那我們按照死線先後順序來做這些工作並不會讓我們少做甚麼工作。這代表我們可以按照死線先後順序來挑工作做。考慮直接暴力 DP 要挑哪些工作，這裡 $\text{dp}_{i,j}$ 代表只做前 $i$ 個工作 (排好序後的前 $i$ 個) 的話，那第 $j$ 天時可以獲得多少報酬，轉移的話就直接在每個時間點都安排看看工作就好了。

#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;
constexpr int N = 5000 + 5;

struct Task {
	int d, c;
	lld s;
};

lld dp[2][N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	vector<Task> a(n);
	for (auto &a_i : a) {
		cin >> a_i.d >> a_i.c >> a_i.s;
	}
	sort(a.begin(), a.end(), [](const auto &x, const auto &y){
		return x.d < y.d;
	});
	int me = 0, he = 1;
	for (int i = 0; i < n; ++i) {
		auto &task = a[i];
		for (int j = 1; j < N; ++j)
			dp[me][j] = dp[he][j];
		for (int j = 1; j <= task.d - task.c + 1; ++j) {
			dp[me][j + task.c] = max(dp[me][j + task.c], dp[he][j] + task.s);
		}
		swap(me, he);
	}
	cout << *max_element(dp[he], dp[he] + N) << '\n';
	return 0;
}