本文共 1058 字，大约阅读时间需要 3 分钟。

题目描述

宣文胜的家乡山西省是我国的产煤大省，因为长期挖煤导致了他家乡的某些地方出现了地陷的情况。 近几年国家大力开展环境整治和土地复耕，让人民不仅享受经济发展所带来的红利更要还老百姓绿水 青山。为了把这些地陷的土地恢复平整，他的家乡决定聘请他负责这项工作。

他负责恢复的是一条长度为n的土地，恢复土地的主要工作是填平下陷的地表。需要恢复的土地可以 看作是n块首尾相连的区域，一开始，第i块区域下陷的深度为di。宣文胜决定每天选择一段连续区间 [M, N] ，填充这段区间中的每块区域，让其下陷深度减少1。在选择区间时，需要保证，区间内的每 块区域在恢复前下陷深度均不为0 。

宣文胜希望你能帮他设计一种方案，可以在最短的时间内将整块土地的下陷深度都变为0。

输入格式

第一行输入一个整数n，表示恢复土地的长度。
第二行n个整数di，以空格隔开。

输出格式

输出一个整数，即最少需要多少天才能完成任务。

输入输出样例

输入 #1

64 3 2 5 3 5

输出 #1

9

输入 #2

42 5 3 5

输出 #2

7

输入 #3

122 6 5 8 9 12 15 7 5 10 16 24

输出 #3

35

说明/提示

数据范围

对于60%的数据，1 ≤ n ≤ 50;
对于80%的数据，1 ≤ n ≤ 1000;
对于100%的数据，1 ≤ n ≤ 100000，0 ≤ di ≤ 10000 。

样例解释

样例1解释说明：
一种可行的最佳方案是，依次选择:
[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。

解题思路

贪心
假设填凹陷时是一排一排填的

如果当前凹陷比前面的凹陷浅，不会对答案有影响
如果当前凹陷比前面的凹陷深，前面填坑的高度只到前面凹陷的的深度，所以当前凹陷 - 前面凹陷的深度 = 需要再填的深度

#include <iostream>#include <cstdio>using namespace std;int n;long long ans, a[1001000];int main(){   	scanf ("%d", &n);	for (int i = 1; i <= n; i++)	{   	     scanf ("%lld", &a[i]);	     if (a[i] > a[i - 1])	         ans += a[i] - a[i - 1];	}	printf ("%lld", ans);}

转载地址：http://dkiq.baihongyu.com/