Greedy Pie Eaters

题目描述

农夫约翰有 $M$ 头奶牛，方便起见编号为 $1\ldots M$，它们偶尔也想换换口味，不只吃草。作为奖励，农夫约翰烤了 $N$ 个派（$1 \leq N \leq 300$），编号为 $1\ldots N$。奶牛 $i$ 喜欢编号在区间 $[l_i, r_i]$（从 $l_i$ 到 $r_i$，包含端点）内的派，并且任意两头奶牛喜欢的派区间都不完全相同。奶牛 $i$ 还有一个重量 $w_i$，是 $1\ldots 10^6$ 范围内的整数。

农夫约翰可以选择一个奶牛序列 $c_1,c_2,\ldots,c_K$，之后被选中的奶牛将按该顺序轮流吃派。不幸的是，奶牛们不会分享！当轮到奶牛 $c_i$ 吃时，她会吃掉所有她喜欢的派——也就是当前仍然剩下的、位于区间 $[l_{c_i},r_{c_i}]$ 内的所有派。农夫约翰希望避免出现这样尴尬的情况：轮到某头奶牛吃时，她喜欢的派已经全部被吃完了。因此，请你计算在满足序列中每头奶牛至少能吃到一个派的前提下，序列 $c_1,c_2,\ldots,c_K$ 的总重量 $w_{c_1}+w_{c_2}+\ldots+w_{c_K}$ 的最大可能值。

输入格式

第一行包含两个整数 $N$ 和 $M$ $\left(1\le M\le \frac{N(N+1)}{2}\right)$。 接下来 $M$ 行每行用整数 $w_i, l_i, r_i$ 描述一头奶牛。

输出格式

输出一个整数，表示一个合法序列的最大可能总重量。

2 2
100 1 2
100 1 1

200

提示

评分： 测试点 2-5 满足 $N\le 50$ 且 $M\le 20$。 测试点 6-9 满足 $N\le 50$。

在这个例子中，如果 1 号奶牛先吃，那么 2 号奶牛将没有任何派可吃。然而，如果 2 号奶牛先吃，那么 1 号奶牛只吃第二个派也会满足。 题目来源：Benjamin Qi

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum