你有nnn个任务，其中第iii个任务，在sis_isi​开始，eie_iei​时刻结束，如果做这个任务，你能获得wiw_iwi​的收益。

但是你在一个时刻只能做一个任务，问选择哪些任务，能让你的收益尽量大。

注意：你在上一个任务结束后马上开始下一个任务是可以的。

输入格式

第一行一个整数nnn。

接下来nnn行，每行三个整数sis_isi​,eie_iei​,wiw_iwi​。

输出格式

一个数，表示答案。

样例输入

3
1 3 100
2 4 199
3 5 100

样例输出

200

数据规模

对于所有数据，保证1≤n≤103,1≤si

解题思路

本题是一道非常规的、同时也是非常好的动态规划题目，具体的“非常规”体现在DP的思路上，接下来说明解题思路

题意抽象来说就是给了起止111~100010001000区间范围内的多条线段，每条线段有自己的权重，选择的线段不能重叠，问如何选使得得到的线段权重最大

很明显，这是一道动态规划问题，那么如何动态规划？

动态规划的关键在于如何从子问题推出更复杂问题的答案

首先我们尝试确定一个子问题的状态：

（1）当前可以得到的最大权重

（2）当前的截止时间

（3）当前考虑的线段数量

先试一下根据（3）展开动态规划，也就是按照常规背包问题的思路

我们会发现我们无法从只考虑前i - 1个物品的情况推导出前i个物品的情况

比如说有如下三条线段

1 2 10
1 3 20
2 4 100

只考虑前两条线段的时候我们可以得到的最大值是20，也就是选择第2条线段

但是我们如果选择第2条线段，我们就不能得到选择1、3线段的最优解

所以我们换一个角度考虑，有关线段覆盖的问题，终止时间是很重要的

如果到终止时间i之前的最大值是已知的，那么我们就只需要考虑i之后的最大值了

从这里我们可以看出最优子结构的存在

那么尝试一下动态规划，还是这样三条线段

1 2 10
1 3 20
2 4 100

考虑截止时间为3时的最大值，是20

好像我们还是不能从截止时间为3时的最大值推出截止时间为4时的最大值

所以说这道题是一道“非常规”的动态规划问题

我们不是在尝试用截止时间为i - 1时的情况推导出截止时间为i时的情况

而是尝试用截止时间为i时的情况去更新之后所有情况的最大值

for (int i = 1; i < max_se; i++) {dp[i + 1] = max(dp[i + 1], dp[i]);for (int j = 1; j <= n; j++) {if (i == tasks[j].s) {dp[tasks[j].e] = max(dp[tasks[j].e], dp[i] + tasks[j].w);}}
}

我们实现了在到达dp[i]之前，尝试过了所有可能的情况，保证了dp[i]是最优解

然后去尝试所有起始时间是i的任务，更新之后的所有元素

最后，AC代码如下

#include 
using namespace std;
const int max_n = 1e3;
const int max_se = 1e3;
const int max_w = 1e5;struct task { int s, e, w; }tasks[max_n + 1];
int dp[max_se + 1], n;int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> tasks[i].s >> tasks[i].e >> tasks[i].w;}for (int i = 1; i < max_se; i++) {dp[i + 1] = max(dp[i + 1], dp[i]);for (int j = 1; j <= n; j++) {if (i == tasks[j].s) {dp[tasks[j].e] = max(dp[tasks[j].e], dp[i] + tasks[j].w);}}}cout << dp[max_se] << endl;return 0;
}