思路:使用分治,在每个连续区域递归调用heng()和shu()
#include <bits/stdc++.h>
using namespace std;
int n, m;
int h[5005];
int shu(int l, int r)
{
return r - l + 1;
}
int heng(int l, int r)
{
int hmin = 0x3f3f3f3f;
for (int i = l; i <= r; i++)
{ // 取高度的最低值,底下的全部横着刷
hmin = min(h[i], hmin);
}
for (int i = l; i <= r; i++)
{ // 还剩下的没刷的
h[i] -= hmin;
}
int ans = hmin;
while (l <= r)
{
while (l <= r && h[l] == 0)
{ // while结束后,l为高度不为0的左边界
l++;
}
int temp = l; // 从l开始的连续区域
while (temp <= r && h[temp] != 0)
{ // temp为高度不为0的右边界的下一位
temp++;
}
// 此时计算l-temp区域(对这一区域进行递归调用)
ans += min(heng(l, temp - 1), shu(l, temp - 1));
l = temp; // 继续下一区域
}
return ans;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> h[i];
cout << min(heng(1, n), shu(1, n));
}