題目：

題目背景

NOIP2018 提高組 D1T1

題目描述

春春是一名道路工程師，負責鋪設(shè)一條長度為?n?的道路。

鋪設(shè)道路的主要工作是填平下陷的地表。整段道路可以看作是?n?塊首尾相連的區(qū)域，一開始，第?i?塊區(qū)域下陷的深度為?di?。

春春每天可以選擇一段連續(xù)區(qū)間?[L,R]?，填充這段區(qū)間中的每塊區(qū)域，讓其下陷深度減少?$1$。在選擇區(qū)間時，需要保證，區(qū)間內(nèi)的每塊區(qū)域在填充前下陷深度均不為?$0$?。

春春希望你能幫他設(shè)計一種方案，可以在最短的時間內(nèi)將整段道路的下陷深度都變?yōu)?$0$?。

輸入格式

輸入文件包含兩行，第一行包含一個整數(shù)?n，表示道路的長度。 第二行包含?n?個整數(shù)，相鄰兩數(shù)間用一個空格隔開，第?i?個整數(shù)為?di?。

輸出格式

輸出文件僅包含一個整數(shù)，即最少需要多少天才能完成任務(wù)。

輸入輸出樣例

輸入?

6 ? 4 3 2 5 3 5

輸出

9

說明/提示

【樣例解釋】

一種可行的最佳方案是，依次選擇：?$[1,6]$、$[1,6]$、$[1,2]$、$[1,1]$、$[4,6]$、$[4,4]$、$[4,4]$、$[6,6]$、$[6,6]$。

【數(shù)據(jù)規(guī)模與約定】

對于?$30\%$?的數(shù)據(jù)，1≤n≤10?；
對于?$70\%$?的數(shù)據(jù)，1≤n≤1000?；
對于?$100\%$?的數(shù)據(jù)，1≤n≤100000,0≤di≤10000?。

題目大意：

輸入數(shù)字n,表示數(shù)組的長度，每次只能在一個連續(xù)的區(qū)間里全部減1，直到全部為0為止，最少操作多少次

思路：

考了貪心算法

從第一個數(shù)字開始來判斷下一步到底需不需要加操作次數(shù)，先記錄第一個坑要操作多少次（這個操作數(shù)是只可能增加不可能減少的，操作次數(shù)肯定會至少大于等于全部坑深度里面最深的那一個坑的深度），與第二個坑的深度作比較，有兩種情況：

1）第二個坑比第一個坑大

填第一個坑的時候會連著填了一點第二個坑，第二個坑沒填完要繼續(xù)填，所以要加操作數(shù)：

操作數(shù)[i-1]=操作數(shù)[i]+坑[i]-坑[i-1];

2）第二個坑小于等于第一個坑

填一個坑的時候第二個坑也已經(jīng)被連著填完了，所以不需要增加操作數(shù)：

操作數(shù)[i]=操作數(shù)[i-1];

循環(huán)……

輸出最后的操作數(shù)

易錯點：

不知道怎么寫，我直接看了別人的題解（采購一個）

代碼：

#include <iostream>

using namespace std;

int ans[100005],rode[100005],n;

int main()

{

? ? cin>>n;

? ? for(int i=0;i<n;i++)cin>>rode[i];

? ? ans[0]=rode[0];

? ? for(int i=1;i<n;i++)

? ? ? ? if(rode[i]<=rode[i-1]) ans[i]=ans[i-1];

? ? ? ? else ans[i]=ans[i-1]+rode[i]-rode[i-1];

? ? cout<<ans[n-1];

}