思路:使用分治,在每个连续区域递归调用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)); }