洛谷P1969「NOIP 2013 / 2018」《积木大赛》

一月 22, 2019 3146

原 题 警 告

题目描述

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为 n 的大厦，大厦可以看成由 n 块宽度为1的积木组成，第 i 块积木的最终高度需要是 h_i 。

在搭建开始之前，没有任何积木（可以看成 n 块高度为 0 的积木）。接下来每次操作，小朋友们可以选择一段连续区间 [l, r] ，然后将第 L 块到第 R 块之间（含第 L 块和第 R 块）所有积木的高度分别增加 1 。

小 M 是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。

输入输出格式

输入格式

包含两行，第一行包含一个整数nn，表示大厦的宽度。

第二行包含 n 个整数，第i个整数为 h_i 。

输出格式

建造所需的最少操作数。

输入输出样例

输入样例

1
2
5
2 3 4 1 2

输出样例

1
5

说明

【样例解释】

其中一种可行的最佳方案，依次选择

[1,5] [1,3] [2,3] [3,3] [5,5]

【数据范围】

对于 30%30%的数据，有 1 ≤ n ≤ 10 ；

对于 70%70%的数据，有 1 ≤ n ≤ 1000 ；

对于 100%100%的数据，有 1 ≤ n ≤ 100000,0 ≤ h_i≤ 10000 。

解题思路

真不敢相信 CCF 居然用了原题

单独把 h_1 读进来，存在 ans 里。

在读剩下的 n - 1 个数的时候，每次判一下当前数与上一个数的关系：

  • 如果比上一个数大，就说明我们还需要再放积木，答案累加当前数与上一个数的差；
  • 如果没有上个数大，就说明我们之前搭积木已经能够把这摞积木放好了，自然就不需要更新了。

然后把「上一个数」更新为当前数即可

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    
}

signed main() {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    int n = 0;
    std::cin >> n;
    int ans = 0;
    std::cin >> ans;
    int lastOne = ans;
    for (int i = 2; i <= n; ++i) {
        int now;
        std::cin >> now;
        if (now > lastOne) ans += (now - lastOne);
        lastOne = now;
    }
    std::cout << ans << std::endl;
    return 0;
}