题目链接
思路
利用的是最长上升子序列的思路，先把每个时间段按开始时间排序，然后dp，以每个时间段作为结尾时的最大价值。
fif_ifi? 表示以第i个时间段结尾的最大的价值
代码
#include<bits/stdc++.h>
using namespace std;
struct name{
int l, r;int x;
};
const int N = 1005;
vector<name> v;
bool cmp(name a, name b)
{
return a.l < b.l;
}
int f[N];
int n, m, k;
int main()
{
while (cin >> n >> m >> k){
memset(f, 0, sizeof f);for (int i = 1; i <= m; i ++ ){
int a, b, c;cin >> a>> b >> c;v.push_back({
a, b + k, c});}sort(v.begin(), v.end(), cmp);int res = 0;for (int i = 0; i < v.size(); i ++ ){
f[i] = v[i].x;for (int j = 0; j < i; j ++ ){
if (v[i].l >= v[j].r){
f[i] = max(f[i], f[j] + v[i].x);}}res = max(res, f[i]);}cout << res << endl;}return 0;
}
总结
参考：https://yiqzq.blog.csdn.net/article/details/80358289
这道题以前就遇见过，可惜不会写，今天再次遇见还是不会写，看了题解，理解了代码，可是还是不太理解为什么，大概可能就是基于最长上升子序列算最大价值吧……
到底要怎么样才能精通dp呢，感觉对于一道题再怎么钻似乎也没有什么特别显著的效果。