The Bucket List

题目描述

农夫 John 正在考虑改变他为奶牛挤奶分配桶的方式。他认为这样最终可以只使用较少数量的桶，但他不确定具体需要多少。请你帮助他！ 农夫 John 有 $N$ 头奶牛（$1 \leq N \leq 100$），方便起见编号为 $1 \ldots N$。第 $i$ 头奶牛需要在时间 $s_i$ 到时间 $t_i$ 之间挤奶，并且在挤奶过程中需要使用 $b_i$ 个桶。可能会有多头奶牛同时在挤奶；如果是这样，它们不能使用同一批桶。也就是说，分配给奶牛 $i$ 挤奶的桶，在时间 $s_i$ 到时间 $t_i$ 之间不能被用于其他任何奶牛的挤奶。当然，在这个时间窗口之外，桶可以被其他奶牛使用。 为简化工作，FJ 确保在任意时刻，最多只有一头奶牛的挤奶开始或结束（也就是说，所有的 $s_i$ 和 $t_i$ 都互不相同）。 FJ 有一个储物间，里面的桶按顺序编号并贴有标签 1、2、3……。在他当前的挤奶策略中，每当某头奶牛（例如奶牛 $i$）开始挤奶（在时间 $s_i$），FJ 就跑到储物间，取出当前可用标签中最小的 $b_i$ 个桶，并将它们分配给奶牛 $i$ 挤奶。 请确定为了成功给所有奶牛挤奶，FJ 的储物间总共需要准备多少个桶。

输入格式

第一行输入为 $N$。接下来的 $N$ 行每行描述一头奶牛，包含 $s_i$、$t_i$ 和 $b_i$，以空格分隔。$s_i$ 和 $t_i$ 均为 $1 \ldots 1000$ 范围内的整数，$b_i$ 为 $1 \ldots 10$ 范围内的整数。

输出格式

输出一个整数，表示 FJ 需要的桶的总数量。

3
4 10 1
8 13 3
2 6 2

4

提示

在这个例子中，FJ 需要 4 个桶：他用桶 1 和 2 给奶牛 3 挤奶（从时间 2 开始）。他用桶 3 给奶牛 1 挤奶（从时间 4 开始）。当奶牛 2 在时间 8 到来时，桶 1 和 2 已经可用，但桶 3 仍不可用，因此他使用桶 1、2 和 4。 题目作者：Brian Dean

标签: USACO|2018|Bronze

来源

USACO|2018|Bronze