记录编号	81860	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]积木大赛	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2013-11-18 22:12:19	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
using namespace std;
const int SIZEN=100001;
int h[SIZEN]={0};
int n;
class COUPLE{
public:
	int lh,rh;
	int opn;//操作数
};
COUPLE DP(int left,int right){
	if(left==right){
		return (COUPLE){h[left],h[left],h[left]};
	}
	int mid=(left+right)>>1;
	COUPLE lf,rf;
	lf=DP(left,mid);
	rf=DP(mid+1,right);
	COUPLE now;
	now.lh=lf.lh,now.rh=rf.rh;
	now.opn=lf.opn+rf.opn-min(lf.rh,rf.lh);
	return now;
}
void read(void){
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++) scanf("%d",&h[i]);
}
int main(){
	freopen("BlockNOIP2013.in","r",stdin);
	freopen("BlockNOIP2013.out","w",stdout);
	read();
	COUPLE ans=DP(1,n);
	printf("%d\n",ans.opn);
	return 0;
}