洛谷笔记 - P1969 [NOIP2013 提高组] 积木大赛

发表于 更新于 本文字数： 586 阅读时长 ≈ 2 分钟

一道题的思路有很多，别在一棵树上吊死。

题目描述

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

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

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

输入格式

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

第二行包含 nn 个整数，第 ii 个整数为 hih_i。

输出格式

建造所需的最少操作数。

样例 #1

样例输入 #1

1
2
5
2 3 4 1 2

样例输出 #1

1
5

提示

【样例解释】

其中一种可行的最佳方案，依次选择：[1,5][1,5]，$ [1,3]，，[2,3]，，[3,3]，， [5,5]$。

【数据范围】

  • 对于 30%30\% 的数据，有 1≤n≤101 \leq n \leq 10；
  • 对于 70%70\% 的数据，有 1≤n≤10001 \leq n \leq 1000；
  • 对于 100%100\% 的数据，有 1≤n≤1000001 \leq n \leq 100000，0≤hi≤100000 \leq h_i \leq 10000。

代码

旧方法

超时大师级别的代码，靠 -O2 捡回一个数据点

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
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,h[100005],ans=0,amx=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
        amx=max(h[i],amx);
    }
    for(int i=1;i<=amx;i++){
        bool flaged=1;
        for(int o=1;o<=n;o++){
            if(h[o]>=i){
                if(flaged){
                    ans++;
                    flaged=0;
                }
            }else{
                flaged=1;
            }
        }
    }
    cout<<ans<<endl;
}

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//P1969 [NOIP2013 提高组] 积木大赛
//https://www.luogu.com.cn/problem/P1969

//Tag:模拟,贪心,递归,NOIp 提高组,2013,2018
//https://www.luogu.com.cn/record/84616704

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,ans=0;
    int h[100001];
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=1;i<=n;i++){
        if(h[i]>h[i-1]){ //左小右大加摆放次数，左大右小不管，全层级样式通吃
            ans+=h[i]-h[i-1];
        }
    }
    cout<<ans<<endl;
}