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

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

题目描述

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

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

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

输入格式

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

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

输出格式

建造所需的最少操作数。

样例 #1

样例输入 #1

5
2 3 4 1 2

样例输出 #1

提示

【样例解释】

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

【数据范围】

对于 $30\%$ 的数据，有 $1 \leq n \leq 10$；
对于 $70\%$ 的数据，有 $1 \leq n \leq 1000$；
对于 $100\%$ 的数据，有 $1 \leq n \leq 100000$，$0 \leq h_i \leq 10000$。

代码

旧方法

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

#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代码

//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;
}