$$\mathrm{工作}$$

题目链接：$\mathrm{S}\mathrm{S}\mathrm{L}1326$

题目

这次故事的主角是 HG ！转眼 $4$ 年过去了， HG 本科毕业了，于是找了份工作。每天 HG 会收到一份任务清单，清单上列出了 $n$ 个可能需要他完成的任务。每个任务包含 $3$ 个信息： $T_i$ 、 $A_i$ 、 $B_i$ ， $T_i$ 表示完成此任务需要的时间， $A_i$ 表示此任务的到达时间， $B_i$ 表示此任务的最晚完成时间。在某一时刻若 HG 手上没有任务，那么他可以选择一个已经到达且还能够在 $B_i$ 时刻之前（或者恰好在 $B_i$ 时刻）完成的任务来做。

由于 HG 有点懒（纯属虚构:D），他想尽量少的减少他的总工作时间，但是他不能在可以做任务的时候故意不做（这样会被炒鱿鱼的>_<），那么他该如何挑选任务来做呢？

你的任务就是求出 HG 的最少工作时间（即总共有多少时间 HG 在做任务）。

输入

第一行一个整数 $n$ 表示任务数。
以下 $n$ 行，每行三个整数 $T_i,A_i,B_i$ 。（ $n<=1000$ ， $0<=A_i,B_i<=1500$ ， $T_i>=1$ ）

输出

输出仅一个数，即最少工作时间。

样例输入

3
15 0 25
50 0 90
45 15 70

样例输出

50

数据范围

$T_i>=1$ ， $0<=A_i,B_i<=1200$ ；
$30\%$ 的数据满足 $n<=5$ ；
$60\%$ 的数据满足 $n<=500$ ；
$100\%$ 的数据满足 $n<=1000$ 。
输入数据保证 $B_i-A_i$ 要大于等于 $T_i$ ，且小于 $2T_i$ 。

思路

这道题是一道 dp 。

就设 $f[i]$ 为到时间 $i$ 最少工作多久（一定要把工作做完）。
就枚举 $i$ 为时间，再枚举工作 $j$ ，如果这个工作可以在 $i$ 的时候开始并做完，就 $f[i+t[j]]=min(f[i+t[j],f[i]+t[j])$ 。
（ $t[j]$ 为这份工作需要的时间）

如果这个时间莫得工作，就从 $f[i-1]$ 转移过来。

最后输出 $f[t]$ ， $t$ 为最后一份工作完成的时间。

代码

#include<cstdio>
#include<iostream>

using namespace std;

int n, t[2001], a[2001], b[2001], f[2001], s = 2147483647, ss = -2147483647;
bool tt;

int main() {
	scanf("%d", &n);//读入
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d", &t[i], &a[i], &b[i]);
		s = min(s, a[i]);//找出边界
		ss = max(ss, b[i]);
	}
	
	for (int i = s; i <= ss; i++)
		f[i] = 2147483647;//初始化
	
	f[s] = 0;
	for (int i = s; i <= ss; i++) {//枚举时间
		if(f[i] != 2147483647) {
			tt = 1;
			for (int j = 1; j <= n; j++) {//枚举工作
				if (a[j] <= i && i + t[j] <= b[j]) {//这个工作可以在这个时间完成
					tt = 0;
					f[i + t[j]] = min(f[i + t[j]], t[j] + f[i]);//dp转移
				}
			}
			if(tt) f[i + 1] = min(f[i + 1], f[i]);//没事干
		}
	}
	
	printf("%d", f[ss]);//输出
	
	return 0;
}