| 题目名称 | 3158. 路面修整【加强版】 |
|---|---|
| 输入输出 | grading.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 LGLJ
于2019-06-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：4， 提交：19， 通过率：21.05% | ||||
 LGLJ |
100 | 0.000 s | 0.00 MiB | C++ |
 雾茗 |
100 | 0.000 s | 0.00 MiB | C++ |
|
LGLJ |
100 | 0.011 s | 7.43 MiB | C++ |
 梦那边的美好ET |
100 | 0.133 s | 34.03 MiB | C++ |
 Hale |
30 | 0.015 s | 13.66 MiB | C++ |
|
雾茗 |
30 | 0.025 s | 13.66 MiB | C++ |
|
雾茗 |
30 | 0.035 s | 13.66 MiB | C++ |
|
雾茗 |
30 | 0.036 s | 13.66 MiB | C++ |
|
雾茗 |
30 | 0.038 s | 13.66 MiB | C++ |
|
雾茗 |
20 | 0.023 s | 13.66 MiB | C++ |
| 关于 路面修整【加强版】 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
[cogs 2969]路面修整
[cogs 3158]路面修整[加强版] [cogs 3160]路面修整[超强版] LGLJ
2019-06-02 19:20
3楼
| ||||
|
感谢ZJB大佬的验题！！！
致歉：由于原题数据与改题人过于水，所以并没有考虑下降的情况，蒟蒻到认为原程序包括了这一情况，由于改题人较懒，就把下降的情况去掉了，致歉！！！ LGLJ
2019-06-02 15:49
2楼
| ||||
|
LINYIN has been hacked the Rank 1
 瑆の時間~無盡輪迴·林蔭
2019-06-01 17:53
1楼
| ||||
【题目描述】
ZHF由于手受伤在家，闲于无聊，又没法打LOL，只好仿照FJ修理自己的农场。
ZHF打算向FJ学习也好好修整一下自己农场中某条凹凸不平的土路。按奶牛们的要求，修好后的路面高度必须满足（毕竟ZHF家的奶牛比较有个性）单调上升，也就是说，高度上升的路段不能同时出现在修好的路中。整条路被分成了 $N(1\le N\le 2,000)$ 段，$N$ 个整数 $A_1,A_2,\dots ,A_N(0\le A_i\le 1,000,000,000)$ 依次描述了每一段路的高度。ZHF 希望找到一个恰好含 $N$ 个元素的单调上升序列 $B_1,\dots , B_N$，作为修过的路中每个路段的高度。由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为： $\vert A_1-B_1\vert +\vert A_2 -B_2\vert +\dots +\vert A_N-B_N\vert$ 请你计算一下，ZHF 在这项工程上的最小支出是多少。ZHF 向你保证，这个支出不会超过 $2^{31}-1$。
【输入格式】
第 $1$ 行：输入 $1$个整数 $N$。
第 $2\dots N+1$ 行：第 $i+1$ 行为 $1$ 个整数 $A_i$。
【输出格式】
第 $1$ 行：输出 $1$ 个正整数，表示ZHF把路修成高度上升的最小花费。
【样例输入】
7 1 3 2 4 5 3 9
【样例输出】
5
【提示】
在此键入。
【来源】
由LGLJ改编