题目描述

其实这道题和积木大赛毫无区别…直接复制粘贴都过了…

算法1

C++ 代码

#include <iostream>
using namespace std;

int h[100010],sum;
void build(int l,int r)
{
    if(l>r) return;
    if(l==r)
    {
        sum+=h[l];
        h[l]=0;
        return;
    }
    int zero[10010],k=0,i,min=h[l];
        for(i=l+1;i<=r;i++) if(h[i]<min&&h[i]!=0) min=h[i];
        sum+=min;
        for(i=l;i<=r;i++) {h[i]-=min;if(h[i]==0) zero[k++]=i;}
    build(l,zero[0]-1);
    for(i=0;i<k-1;i++) build(zero[i]+1,zero[i+1]-1);
    build(zero[k-1]+1,r);
}
int main()
{
    int n,i,zero[10010],k=0;bool b=false;
    cin>>n;
    for(i=0;i<n;i++) {cin>>h[i];if(h[i]==0) {zero[k++]=i;b=true;}}
    if(b)
    {
        build(0,zero[0]-1);
        for(i=0;i<k-1;i++) build(zero[i]+1,zero[i+1]-1);
        build(zero[k-1]+1,n-1);
    }
    else build(0,n-1);
    cout<<sum;
    return 0;
}