记录编号	309452	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]积木大赛	最终得分	100
用户昵称	BillAlen	是否通过	通过
代码语言	C++	运行时间	0.082 s
提交时间	2016-09-19 19:24:10	内存使用	0.63 MiB

#include <iostream>
#include <fstream>
#include <cmath>
#define MAX_N 100000
#define MAX_H 10000
using namespace std;
int n, h[MAX_N];
int rec(int l, int r){ // 区间左开右闭
    if(l >= r) return 0;
    int imin = MAX_H + 10, pos = -1;
    for(int i = l; i < r; ++i)
        if(h[i] < imin){
            imin = h[i];
            pos = i;
        }
    for(int i = l; i < r; ++i)
        h[i] -= imin;
    return imin + rec(l, pos) + rec(pos + 1, r);
}
int main()
{
    fstream in("BlockNOIP2013.in", ios::in), out("BlockNOIP2013.out", ios::out);
	in >> n;
    for(int i = 0; i < n; ++i)
        in >> h[i];
    out << rec(0, n);
    return 0;
}