题解 P1969 【积木大赛】
iwprc
2017-08-15 17:19:25
这道题我用了分治的方法，如果当前要计算搭建区间[l,r]
所需要的操作数，那么它就等于左右两个区间的操作数之和
减去两个区间连接部分的最小值，因为重复了，所以两边可
以连接起来。
f(l,r)=f(l,mid)+f(mid+1,r)-min(h[mid],h[mid+1])
代码：
```cpp
#include<cstdio>
short h[100000];
int n,i;
short min(short x,short y){return x<y?x:y;}
int f(int l,int r){
if(l==r)
return h[l];
int mid=l+r>>1;
return f(l,mid)+f(mid+1,r)-min(h[mid],h[mid+1]);
}
int main(){
scanf("%d",&n);
for(;i<n;i++)
scanf("%hd",h+i);
printf("%d",f(0,n-1));
return 0;
}
时间复杂度：O(2n)
```