传送门

题意说给n个高度为ai的板子，你可以用宽度为1的刷子横着涂色或者竖着涂色，当遇到空隙或者边缘的时候停止，不可以拐弯。问最少多少次能涂完。

做法是贪心，对于一个区间，如果我要横着涂，那些能一笔涂完的地方我一定要一笔涂完。

而对于一个矩形，很容易算出来到底横着还是竖着划算。

于是对于每个区间，我先把能横着涂的涂完（一个矩形），然后递归没涂的两个部分。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 233;
int a[N];
int solve(int l, int r, int u)
{
    if(l > r) return 0;
    int h = a[l], idx = l;
    for(int i = l; i <= r; i++) h = a[i] < h ? a[idx = i] : h;
    return min(r - l + 1, solve(l, idx - 1, h) + h - u + solve(idx + 1, r, h));
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    cout << solve(1, n, 0) << endl;
}