题目描述

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

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

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

 

输入

输入包含两行，第一行包含一个整数n，表示大厦的宽度。 第二行包含n个整数，第i个整数为ℎi。

 

题解思路：这个题之前在atcode中做过用的是，每次都减1，判断连续实数区间的个数。但是，将这个题放到这接着就T掉了，因为数据太大，所以我们应该换一下思路了。仔细想想，要求这个题的解就是每个连续递增区间的差值，为什么？我们拿2 3 4 1 2来做一下实例

我们以sum为最大和，now为现在的项，pre为前一项

第一步：令now=2，即该数列的首项。sum+=now，说明如果只有一个元素，搭建now次。

第二步：判断now是否大于pre：

(1)next>now：说明now可以跟pre之前的区间连续，他可以一起被搭建，但之后需要单独搭建（next-now）次。

(2)next<now：说明now也可以pre之前区间连续，但是此时的now被一定被之前的pre搭建过了，所以就不需要加了。

第三步：重复以上两步，如果第二步属于(2)，那么则就说明出现了断点，所以继续重复上面的两步，总而言之第三步就是重复上面两步。

下面我们拿2 3 4 1 2进行演示:

  1. 首先令2为第一项。然后从第二项开始，sum=now，有一个搭建他的高度次就可以了。
  2. now=3,pre=2,则说明前两项可以通过先拿两次，再拿一次，也就是sum+=now-pre。
  3. now=4,pre=3,与第二步相同。
  4. now=1,pre=4,小于说明在这之前存在一个连续区间，已经将now搭建了，我们就不需要管了，sum=sum。
  5. now=2,pre=1,又开始上升，但此时已经出现了断点，因为之前被搭建过了，所以只需要sum+=now-pre。
  6. 结束，输出sum

最后附一下代码：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <sstream>
#include <vector>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const ll INF=1e9;
/*中国有句古话，叫作置之死地而后生*/
/*Wrod in CHina,killing make you Stronger*/
int num[maxn];
int cop[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);
    int x=num[1];
    int s=num[1];
    for(int i=2;i<=n;i++)
    {
        if(num[i]>s) x+=(num[i]-s);
        s=num[i];
    }
    printf("%d\n",x);
    return 0;
}

该题类似于动态规划，还有好多网络大神解法，我觉得这种是最简单的一种，便写了博客，防止以后忘了，这种题还是比较常见的。