题目描述

Chnlkw为了计算一天能干多少事，他将一天划分为 $n$ 个单位时间，并告诉你这天他可以干 $m$ 项工作。其中第 $i$ 项工作需要从第 $S_i$ 个时刻开始连续做到 $E_i$ 个时刻为止才能完成，完成这项工作可以获得 $P_i$ 的收入。

Chnlkw某一时刻只能做一项工作，且一旦开始某项工作就必须不间断地一次性做完。问他这一天能获得最大的收入。

输入格式

第 $1$ 行两个整数 $n$，$m$ 表示 $n$ 个时刻与 $m$ 项工作

接下来 $m$ 行，表示 $m$ 项工作，每行 $3$ 个整数 $S_i$，$E_i$，$P_i$

输出格式

一行一个整数，表示最大收入

---

30pts

#include<bits/stdc++.h>
using namespace std;
int f[100005];int p[100005];
vector<pair<int,int> >vec[100005];
int main(){
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;cin>>x>>y>>z;
		vec[y].push_back(make_pair(x,z));
	}
	for(int i=1;i<=n;i++){
		f[i]=max(f[i],f[i-1]);
		for(int j=0;j<vec[i].size();j++){
			f[i]=max(f[vec[i][j].first]+vec[i][j].second,f[i]);
		}
//		cout<<f[i]<<' ';
	}
	cout<<f[n];
}