这是我的解题报告，时间复杂度O（n） 大家加油吧！
http://blog.csdn.net/qq_35904657/article/details/62220896

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 100005;

int h[M];

int main()
{
int n, ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &h[i]);
if(h[i] < h[i-1]) ans += h[i-1] - h[i];
}
ans += h[n];
printf("%d", ans);
return 0;
}

这个题其实代码没任何难度，懂了原理肯定是会写的
所以说这道题主要是想一下原理

原题意是需要最后建成长度为n的一个建筑物，也就是这个建筑物宽度为n

不妨将其视作要求建造一个长度为n+1的建筑物（0-n） 第0个位置高度为0

那么则有：

a[i]表示第i个位置的高度

(1)若a[i]<=a[i-1]
则a[i]是完全不需要考虑的，因为在能够搭建a[i-1]高度的同时向右延伸就顺便建造了
(2)当a[i]>a[i-1]
那么a[i]-a[i-1]的部分就需要在a[i]另外去建造，所以ans+=a[i]-a[i-1]

结束

#include<bits/stdc++.h>
using namespace std;
int a[100001];
int main()
{
    int n,ans=0; cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    if(a[i]>a[i-1])
    ans+=(a[i]-a[i-1]);
    cout<<ans;
    return 0;
}

一个小优化，不开数组，空间复杂度O(1);
#1 Accepted 1ms 324.0 KiB
#2 Accepted 1ms 324.0 KiB
#3 Accepted 1ms 316.0 KiB
#4 Accepted 2ms 324.0 KiB
#5 Accepted 1ms 316.0 KiB
#6 Accepted 1ms 324.0 KiB
#7 Accepted 1ms 316.0 KiB
#8 Accepted 2ms 324.0 KiB
#9 Accepted 5ms 316.0 KiB
#10 Accepted 9ms 324.0 KiB

#include<iostream>
#include<algorithm>
using namespace std;
//呵呵
//大神万岁

//结构定义区

//全局变量区
int cur,last,n; 
long long sum=0;
//函数声明区

//主函数开始！
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    last=0;
    for(int i=1;i<=n;i++)
    {
        cin>>cur;
        if(cur>last) sum+=(cur-last);
        last=cur;
    }
    cout<<sum<<endl;
}
//函数实现区

水题
边找拐点边模拟

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,k=0,s=0,m=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(x<k)
        {
            s+=k-m;
            m=x;
        }
        if(i!=n||x<k)
        k=x;
    }
    printf("%d",s+x-m);
    return 0;
}

空间复杂度O(1)；

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n, h, h0 = 0, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> h;
        if (h0 > h)
            ans += h0 - h;
        h0 = h;
    }
    ans += h;
    cout << ans << endl;
    return 0;
}

极限压行

#include<stdio.h>
int i,n,h[100001],ans=0;
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&h[i]); h[n+1]=0;
    for(i=1;i<=n;i++) if(h[i]>h[i+1]) ans+=h[i]-h[i+1];
    printf("%d",ans); return 0;}

分治rmq，每次找出最小值，计算并递归左右区间，记得用一个变量表示之前在这个区间已经搭建了多少
/*program by mangoyang*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define INF (0x7f7f7f7f)
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define N (100005)
#define Pow (18)
using namespace std;
inline void read(int &x){
int w = 1; char ch = 0; x = 0;
while (ch ^ '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
x = x * w;
}
int f[N][Pow+1], g[N][Pow+1], a[N], n, ans;
inline int Rmq(int l, int r){
int d = (double) log2(r - l + 1);
return f[l][d] < f[r-(1<<d)+1][d] ? g[l][d] : g[r-(1<<d)+1][d];
}
inline void solve(int l, int r, int used){
if(l > r) return;
int pos = Rmq(l, r);
ans += a[pos] - used;
solve(l, pos - 1, a[pos]);
solve(pos + 1, r, a[pos]);
}

int main(){
read(n);
memset(f, 33, sizeof(f));
for(int i = 1; i <= n; i++)
read(a[i]), f[i][0] = a[i], g[i][0] = i;
for(int j = 1; j <= Pow; j++)
for(int i = 1; i <= n; i++){
if(i + (1 << j - 1) > n) continue;
if(f[i][j-1] < f[i+(1<<j-1)][j-1])
f[i][j] = f[i][j-1], g[i][j] = g[i][j-1];
else f[i][j] = f[i+(1<<j-1)][j-1], g[i][j] = g[i+(1<<j-1)][j-1];
}
solve(1, n, 0);
printf("%d\n", ans);
return 0;
}

//10行
#include<iostream>
using namespace std;
int n,ans,i,a[100010];
int main()
{ cin>>n;
for(i=1;i<=n;i++)
{cin>>a[i];
if(a[i]-a[i-1]>0)ans+=(a[i]-a[i-1]);}
cout<<ans;
return 0;}

#include<iostream>
#include<cstdio>
using namespace std;
int n,x,p,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x);
int k=x-p;
if(k>0)ans+=k;
p=x;
}
cout<<ans<<endl;
return 0;
}

C++题解+代码
http://www.cnblogs.com/937337156Zhang/p/5664608.html

#include<iostream>
using namespace std;
int h[100001];
int main()
{
    int n,mmin=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(h[i]>h[i-1])
        {
            mmin+=(h[i]-h[i-1]);
        }
    }
    cout<<mmin;
    return 0;
}

1.第一块积木永远是要堆好，才去考虑下一块积木
2.假设第二块积木比第一块高，那么就需要补齐
3.假设第二块积木比第一块低，那么堆第一块积木的时候已经堆好第二块积木
以此类推

o（n）秒过啊啊啊啊啊啊

5555555

#include<iostream>
using namespace std;
int s={0},n,a[1000001]={0};
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>a[i-1]) s=s+a[i]-a[i-1];
}

cout<<s;
return 0;
}
水………………
可是 考试时
竟然爆0了 超空间了

9行......
program p1844;
var a:array[0..100002] of longint;
n,i,sum:longint;
begin
read(n);
for i:=1 to n do read(a[i]);
for i:=0 to n do sum:=sum+abs(a[i+1]-a[i]);
write(sum div 2);
end.

var
i,j,n,m:longint;
ans:int64;
a:array[-1..100000] of longint;
begin
readln(n);
ans:=0;
for i:=1 to n do
read(a[i]);
for i:=1 to n do
if a[i]>a[i-1] then ans:=ans+a[i]-a[i-1];
writeln(ans);
end.

说说咱的做法...
o(nlogn)的算法，没想到o(n)的....
首先可以知道对于区间【s,t】最少的步骤明显就是每一次都选择最低的那块积木，然后整个区间累加到那块积木的高度，然后再递归【s,k-1】和【k+1,t】，所以为了最快的找出区间最小值，要写RMQ的ST算法。
然后就只要递归模拟就可以了。但是由于数据范围超100000，直接递归强一点的数据会爆栈...所以得手写一个人工栈。
模拟的复杂度O(N),ST预处理O(NlogN)...然后就可以了...

var
n,i,j,total:longint;
h:array [1..100000] of longint;

begin
read(n);
for i:=1 to n do read(h[i]);
total:=h[1];
for j:=2 to i do
begin
if h[j-1]<h[j] then inc(total,(h[j]-h[j-1]));
end;
writeln(total);
end.

var
i,j,n,m:longint;
ans:int64;
a:array[-1..100000] of longint;
begin
readln(n);
ans:=0;
for i:=1 to n do
read(a[i]);
for i:=1 to n do
if a[i]>a[i-1] then ans:=ans+a[i]-a[i-1];
writeln(ans);
end.