记录编号	469973	评测结果	AAAAAATTEE
题目名称	1440.[NOIP 2013]积木大赛	最终得分	60
用户昵称	REALIZE_BEYOND	是否通过	未通过
代码语言	C++	运行时间	2.169 s
提交时间	2017-11-03 23:32:43	内存使用	4.17 MiB

#include<cstdio>
#include<iostream>

using namespace std;
int n,h[1005],f[1005][1005];
int dfs(int l,int r){
	if(f[l][r]) return f[l][r];
	if(l==r) return f[l][r]=h[l];
	int Min=10000000,t1,t2;
	for(int i=l;i<r;i++){
		t1=dfs(l,i);
		t2=dfs(i+1,r);
		Min=min(Min,t1+t2-min(h[i],h[i+1]));
	}
	return f[l][r]=Min;
}
int main(){
	freopen("BlockNOIP2013.in","r",stdin);
	freopen("BlockNOIP2013.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&h[i]);
	printf("%d",dfs(1,n));
	return 0; 
}