題干：

題目描述

春春幼兒園舉辦了一年一度的“積木大賽”。今年比賽的內容是搭建一座寬度為nn的大廈，大廈可以看成由n塊寬度為1的積木組成，第i塊積木的最終高度需要是h_ihi?。

在搭建開始之前，沒有任何積木（可以看成nn塊高度為00的積木）。接下來每次操作，小朋友們可以選擇一段連續區間[l, r][l,r]，然后將第第LL塊到第?RR?塊之間（含第LL?塊和第?RR塊）所有積木的高度分別增加11。

小MM是個聰明的小朋友，她很快想出了建造大廈的最佳策略，使得建造所需的操作次數最少。但她不是一個勤于動手的孩子，所以想請你幫忙實現這個策略，并求出最少的操作次數。

輸入輸出格式

輸入格式：

?

包含兩行，第一行包含一個整數nn，表示大廈的寬度。

第二行包含nn個整數，第i個整數為h_ihi?。

?

輸出格式：

?

建造所需的最少操作數。

?

輸入輸出樣例

輸入樣例#1：?復制

5 2 3 4 1 2

輸出樣例#1：?復制

5

說明

【樣例解釋】

其中一種可行的最佳方案，依次選擇

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

【數據范圍】

對于30\%30%的數據，有1 ≤ n ≤ 101≤n≤10；

對于?70\%70%的數據，有1 ≤ n ≤ 10001≤n≤1000；

對于?100\%100%的數據，有1 ≤ n ≤ 100000,0 ≤ h_i≤ 100001≤n≤100000,0≤hi?≤10000。

?

NOIP2018

?． 鋪設道路
(road.cpp/c/pas)
【問題描述】
春春是一名道路工程師，負責鋪設一條長度為 n 的道路。
鋪設道路的主要工作是填平下陷的地表。整段道路可以看作是 n 塊首尾相連的區
域，一開始，第 i 塊區域下陷的深度為 d i 。
春春每天可以選擇一段連續區間 [L,R] ，填充這段區間中的每塊區域，讓其下陷深
度減少 1。在選擇區間時，需要保證，區間內的每塊區域在填充前下陷深度均不為 0 。
春春希望你能幫他設計一種方案，可以在最短的時間內將整段道路的下陷深度都變
為 0 。
【輸入格式】
輸入文件名為 road.in 。
輸入文件包含兩行，第一行包含一個整數 n，表示道路的長度。
第二行包含 n 個整數，相鄰兩數間用一個空格隔開，第 i 個整數為 d i 。
【輸出格式】
輸出文件名為 road.out 。
輸出文件僅包含一個整數，即最少需要多少天才能完成任務。
【輸入輸出樣例 1】
road.in ?road.out
6
4 3 2 5 3 5
9

解題報告：

? 這兩者是一樣的題，在此以積木大賽作為講解。

? ?首先你如果暴力的話會重復算很多次，，，然后你發現相鄰兩者如果高度有個遞增的關系的話，是可以省去第二次的運算的，但是如果高度是遞減的，，那就需要更新高度重新算了，，，看代碼不難理解了。。思路也不是很難想。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int a[MAX]; int main() {int n;int cnt = 0,cur = 0;cin>>n;for(int i = 1; i<=n; i++) scanf("%d",a+i);for(int i = 1; i<=n; i++) {if(a[i] > cur) cnt += (a[i] - cur); cur = a[i];}printf("%d\n",cnt);return 0 ;}

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【NOIP2013积木大赛，NOIP2018铺设道路】积木大赛（思维，贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。