Painting fence

题意

乍一看以为是之前做过的一道单调队列优化的DP，不是。

也是有n块木板，每个木板宽1米，有一个高度a_i，现在要把他们刷成橘色，给了你一个宽一米的刷子，你可以横着刷，或者竖着刷，问最少需要刷几下才能将所有的木板着色。

思路

对于一个区间[l,r]的木板来说，第一步要么把所有的木板都竖着刷，要么把最低的木板横着刷一遍，问题变为区间所有的木板减去最短木板的高度之后，刷分为的两个小区间的次数和+最短木板高度。两者取最小值即可。分治

代码

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int N=1e5+10;

const int mod=1e9+7;

const ll inf=0x3f3f3f3f3f3f3f3f;

const double eps=1e-14;

int arr[N];

int solve(int l,int r)

{

    if(l>r) return 0;

    int pos,minn=inf;

    for(int i=l;i<=r;i++)

    {

        if(arr[i]<minn)

        {

            minn=arr[i];

            pos=i;

        }

    }

    for(int i=l;i<=r;i++) arr[i]-=minn;

    return min(r-l+1,solve(l,pos-1)+solve(pos+1,r)+minn);

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d",&arr[i]);

    printf("%d\n",solve(1,n));

    return 0;

}