[CF448C] Painting Fence - 贪心,分治
Description
有 n ((n le 5000)) 块连着的木板,每个木板的高度为 (h_i),你需要把这 n 块木板上色,每次上色你可以选择竖着刷完一块木板,或者横着刷一个高度单位的连续的木板(中间空着的不能跳跃),问最少需要刷几次。
Solution
贪心分治,要么全刷竖的,要么刷横的直到最小的那个消失,然后分治下去
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5005;
int n, a[N];
int solve(int l, int r, int x)
{
if (l > r)
return 0;
int mn = a[l], mp = l;
for (int i = l; i <= r; i++)
if (a[i] < mn)
mn = a[i], mp = i;
if (mn != x)
return min(solve(l, mp - 1, mn) + solve(mp + 1, r, mn) + mn - x, r - l + 1);
else
return solve(l, mp - 1, mn) + solve(mp + 1, r, mn);
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
cout << solve(1, n, 0) << endl;
}