洛谷P5019 [NOIP2018 提高組] 鋪設道路
題目描述
春春是一名道路工程師，負責鋪設一條長度為 n 的道路。
鋪設道路的主要工作是填平下陷的地表。整段道路可以看作是 n 塊首尾相連的區域，一開始，第 i 塊區域下陷的深度為 di。
春春每天可以選擇一段連續區間[L,R][L,R] ，填充這段區間中的每塊區域，讓其下陷深度減少 1。在選擇區間時，需要保證，區間內的每塊區域在填充前下陷深度均不為 0 。
春春希望你能幫他設計一種方案，可以在最短的時間內將整段道路的下陷深度都變為 0 。
輸入格式
輸入文件包含兩行，第一行包含一個整數 n，表示道路的長度。 第二行包含 n 個整數，相鄰兩數間用一個空格隔開，第i個整數為 di 。
輸出格式
輸出文件僅包含一個整數，即最少需要多少天才能完成任務。
輸入輸出樣例
6 4 3 2 5 3 5
9
說明/提示
【樣例解釋】
一種可行的最佳方案是，依次選擇： [1,6][1,6]、[1,6][1,6]、[1,2][1,2]、[1,1][1,1]、[4,6][4,6]、[4,4][4,4]、[4,4][4,4]、[6,6][6,6]、[6,6][6,6]。
【數據規模與約定】
對於 30% 的數據，1 ≤ n ≤ 101≤n≤10 ；
對於 70% 的數據，1 ≤ n ≤ 10001≤n≤1000 ；
對於 100% 的數據，1 ≤ n ≤ 100000 , 0 ≤ di ≤ 100001≤n≤100000,0≤di≤10000 。
說實話不太好做，我感覺這是個模擬，分析一下；
要想在最短的時間內填坑，就需要能把大坑填了的時候一起把小坑順手也填了，這樣才能發揮貪心的最大策略，我們來拿樣例模擬一下：
用f[i]表示前i個坑所鋪設的最少天數
那麼要做的只需比較一下當前的a[i]和a[i+1]，分兩種情況：
如果a[i]>=a[i+1]，那麼在填a[i]時就可以順便把a[i+1]填上，這樣顯然更優，所以f[i+1]=f[i]
否則的話，那麼在填a[i]時肯定要盡量把a[i+1]一塊填上，a[i+1]剩餘的就單獨填。
所以，f[i+1]=f[i]+a[i+1]-a[i]
初始化f[0]=a[0]
拿樣例，坑深分別是4 ，3，2，5，3，5
先填第一個坑，那後面的3，2都可以天，剩下的坑大於這個坑的深度就要單獨填，那麼，我們設第一個坑為a[0],第一天就是4，
就可以依照上面的結論得出結果
程式碼如下：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[100000]={0};
int f[10000]={0};
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
f[0]=a[0];
for(int i=0;i<n-1;i++)
{
if(a[i]>=a[i+1])
{
f[i+1]=f[i];
}
else
{
f[i+1]=a[i+1]-a[i]+f[i];
}
}
printf("%d",f[n-1]);
return 0;
}
