| 题目名称 | 3053. [NOIP 2018]铺设道路 |
|---|---|
| 输入输出 | 2018road.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 yuan
于2018-11-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：113， 提交：188， 通过率：60.11% | ||||
 syzhaoss |
100 | 0.000 s | 0.00 MiB | C++ |
 LGLJ |
100 | 0.000 s | 0.03 MiB | C++ |
 雾茗 |
100 | 0.000 s | 0.03 MiB | C++ |
|
zhk |
100 | 0.001 s | 0.61 MiB | C++ |
|
lihaoze |
100 | 0.001 s | 0.63 MiB | C++ |
 增强型图元文件 |
100 | 0.001 s | 1.42 MiB | C++ |
|
XCstar |
100 | 0.002 s | 0.57 MiB | C++ |
|
op_组撒头屯 |
100 | 0.002 s | 0.61 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.002 s | 0.65 MiB | C++ |
 Oasiz |
100 | 0.002 s | 1.40 MiB | C++ |
| 本题关联比赛 | |||
| 近5年noip/csp题目回顾 | |||
| 关于 铺设道路 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
看了看DL们的代码，貌似只有我一个傻傻地打了一个ST加分治。。。
| ||||
  霖：404
2020-09-09 21:18
3楼
| ||||
|
本蒟蒻第一道提高组水提，评论留念。
霖：404
2018-12-14 22:07
2楼
| ||||
|
那个0.005s的代码牛逼
 性感荷官在线发牌
2018-11-16 16:25
1楼
| ||||
【题目描述】
春春是一名道路工程师，负责铺设一条长度为 $n$ 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 $n$ 块首尾相连的区域，一开始，第 $i$ 块区域下陷的深度为 $d_i$。
春春每天可以选择一段连续区间 $[L, R]$ ，填充这段区间中的每块区域，让其下陷深度减少 1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 0。春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 0 。
【输入格式】
输入文件包含两行，第一行包含一个整数 $n$，表示道路的长度。
第二行包含 $n$ 个整数，相邻两数间用一个空格隔开，第 $i$ 个整数为 $d_i$ 。
【输出格式】
输出文件仅包含一个整数，即最少需要多少天才能完成任务。
【样例输入1】
6 4 3 2 5 3 5
【样例输出1】
9
【提示】
一种可行的最佳方案是，依次选择：
[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。
【输入输出样例2】
【数据规模与约定】
对于 30% 的数据，$1 ≤ n ≤ 10$ ；
对于 70% 的数据，$1 ≤ n ≤ 1000$ ；
对于 100% 的数据，$1 ≤ n ≤ 100000 ，0≤d_i≤ 10000$ 。
【来源】
NOIP 2018 Day 1 Task 1