#PU972. USACO 2019 December Contest, Platinum — Problem 1. Greedy Pie Eaters

    ID: 1276 传统题 文件IO:pieaters 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec19来源:usaco.orgscoring:equal_test_cases贪心区间DP

USACO 2019 December Contest, Platinum — Problem 1. Greedy Pie Eaters

USACO 2019 December Contest, Platinum — Problem 1. Greedy Pie Eaters

题目描述

Farmer John has MM cows, conveniently labeled 1…M1 \ldots M, who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer John has baked NN pies (1≤N≤3001 \leq N \leq 300), labeled 1…N1 \ldots N. Cow ii enjoys pies with labels in the range [li,ri][l_i, r_i] (from lil_i to rir_i inclusive), and no two cows enjoy the exact same range of pies. Cow ii also has a weight, wiw_i, which is an integer in the range 1…1061 \ldots 10^6. Farmer John may choose a sequence of cows c1,c2,…,cK,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 cic_i's turn to eat, she will consume all of the pies that she enjoys --- that is, all remaining pies in the interval [lci,rci][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 (wc1+wc2+…+wcKw_{c_1}+w_{c_2}+\ldots+w_{c_K}) of a sequence c1,c2,…,cKc_1,c_2,\ldots, c_K for which each cow in the sequence eats at least one pie.

输入格式

The first line contains two integers NN and MM (1≤M≤N(N+1)2)\left(1\le M\le \frac{N(N+1)}{2}\right). The next MM lines each describe a cow in terms of the integers wi,liw_i, l_i, and rir_i.

输出格式

Print the maximum possible total weight of a valid sequence.

数据范围

Test cases 2-5 satisfy N≤50N\le 50 and M≤20M\le 20. Test cases 6-9 satisfy N≤50.N\le 50.

样例

样例 1

2 2
100 1 2
100 1 1
200
In this example, if cow 1 eats first, then there will be nothing left for cow 2 to eat. However,
if cow 2 eats first, then cow 1 will be satisfied by eating the second pie only.
Problem credits: Benjamin Qi