| 题目名称 | 1504. [POJ 1821]粉刷栅栏 |
|---|---|
| 输入输出 | fence_paint.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 syzhaoss
于2014-01-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 查看题解 | 分享题解 |
| 通过：11， 提交：25， 通过率：44% | ||||
 嗨嗨嗨 |
100 | 0.000 s | 1.25 MiB | C++ |
|
whaleeee |
100 | 0.001 s | 1.20 MiB | C++ |
|
wow草原 |
100 | 0.003 s | 2.54 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.003 s | 2.66 MiB | C++ |
|
wow草原 |
100 | 0.004 s | 1.27 MiB | C++ |
|
wow草原 |
100 | 0.006 s | 2.54 MiB | C++ |
|
郑霁桓 |
100 | 0.009 s | 5.60 MiB | C++ |
|
liuyiche |
100 | 0.014 s | 6.07 MiB | C++ |
|
wow草原 |
100 | 0.019 s | 6.19 MiB | C++ |
|
Benjamin |
100 | 0.040 s | 3.81 MiB | C++ |
| 关于 粉刷栅栏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
注意N和M
| ||||
【题目描述】
有 $N$ 块木板从左到右排成一行，有 $M$ 个工匠对这些木板进行粉刷，每块木板至多被粉刷一次。
第 $i$ 个木匠要么不粉刷，要么粉刷包含木板 $S_i$ 且长度不超过 $L_i$ 的连续的一段木板，每粉刷一块可以得到 $P_i$ 的报酬。
不同工匠的 $S_i$ 不同。
请问如何安排能使工匠们获得的总报酬最多。
【输入格式】
第一行包含两个整数 $N$ 和 $M$。
接下来 $M$ 行，每行包含三个整数 $L_i,P_i,S_i$。
【输出格式】
输出一个整数，表示结果。
【样例输入】
8 4 3 2 2 3 2 3 3 3 5 1 1 7
【样例输出】
17
【数据规模与约定】
$1≤N≤16000,1≤M≤100,1≤P_i≤10000.$
【来源】
$POJ$ $1821$
《算法竞赛进阶指南》$0x59$ 例题