任务分配
题目描述
你有 \(n\) 个任务，其中第 \(i\) 个任务，在 \(s_i\) 开始，\(e_i\) 时刻结束，如果做这个任务，你能获得 \(w_i\) 的收益。
但是你在一个时刻只能做一个任务，问选择哪些任务，能让你的收益尽量大。
注意：你在上一个任务结束后马上开始下一个任务是可以的。
输入格式
第一行一个整数 \(n\)。
接下来 \(n\) 行，每行三个整数 \(s_i,e_i,w_i\)。
输出格式
一个数，表示答案。
样例输入
3
1 3 100
2 4 199
3 5 100
样例输出
200
数据范围
对于所有数据，保证 \(1≤n≤10^3,1≤s_i<e_i≤10^3,1≤w_i≤10^5\)。
解题思路
看到这个数据范围以及题目要求收益尽量大，也就是说在一定的时间内，获得最大的收益，因此我们可以采取动态规划来解题。整体思路和最长上升子序列很像。数组 \(f[j]\) 表示在时间 \(1\) 到 \(j\) 这个范围内所能取得的最大收益。状态方程为具体看代码实现。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
typedef long long LL;
int n;
int s[N], e[N], w[N];
int f[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%d%d%d", &s[i], &e[i], &w[i]);
for(int j = 1; j <= 1000; j ++) // 结束时间为 j
{
for(int i = 1; i <= n; i ++)
{
if(j == e[i]) f[j] = max(f[j], f[s[i]] + w[i]);
else f[j] = max(f[j], f[j - 1]);
}
}
printf("%d\n", f[1000]);
return 0;
}