TouchStone
请登录后使用
系统首页 　练习题库 　考试列表 　判题结果 　信息发布 　解题排行
P6554【USACO 2019 Dec Platinum】Greedy Pie Eaters
 限制 : 时间限制 : - MS   空间限制 : - KB 评测说明 : 1s,512m
###### 问题描述

Farmer John 有 $M$ 头奶牛，为了方便，编号为 $1\ldots M$。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。
Farmer John 一天烤了 $N$ 个派请奶牛吃，这 $N$ 个派编号为 $1\ldots N$。第 $i$ 头奶牛喜欢吃编号在 $[l_i,r_i]$ 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 $i$ 头奶牛有一个体重 $w_i$，这是一个在 $[1, 10^6]$ 中的正整数。

Farmer John 可以选择一个奶牛序列 $c_1,c_2,\ldots c_K$，并让这些奶牛按这个顺序轮流吃派。

Farmer John 想要避免当轮到一头奶牛吃派时，她所有喜欢的派在之前都被吃掉了这样尴尬的情况。

Farmer John has $M$ cows, conveniently labeled $1 \ldots M$, who enjoy the occasional change of pace from eating grass.
As a treat for the cows, Farmer John has baked $N$ pies ($1 \leq N \leq 300$), labeled $1 \ldots N$.
Cow $i$ enjoys pies with labels in the range $[l_i, r_i]$ (from $l_i$ to $r_i$ inclusive), and no two cows enjoy the exact same range of pies.
Cow $i$ also has a weight, $w_i$, which is an integer in the range $1 \ldots 10^6$.

Farmer John may choose a sequence of cows $c_1,c_2,\ldots, c_K,$ after which the selected cows will take turns eating in that order.
Unfortunately, the cows don't know how to share!
When it is cow $c_i$'s turn to eat, she will consume all of the pies that she enjoys --- that is,
all remaining pies in the interval $[l_{c_i},r_{c_i}]$.
Farmer John would like to avoid the awkward situation occurring when it is a cows turn to eat but all of the pies she enjoys have already been consumed.
Therefore, he wants you to compute the largest possible total weight ($w_{c_1}+w_{c_2}+\ldots+w_{c_K}$) of a sequence $c_1,c_2,\ldots, c_K$ for which each cow in the sequence eats at least one pie.

#### INPUT FORMAT (file pieaters.in):

The first line contains two integers $N$ and $M$ $\left(1\le M\le \frac{N(N+1)}{2}\right)$.

The next $M$ lines each describe a cow in terms of the integers $w_i, l_i$, and $r_i$.

2 2
100 1 2
100 1 1

200