cf(448c)-painting fence

これは面接問題であり、codeforcesのc類の問題でもある.tags:divide and conquer,dp,greedy
解決策
まず明確にする

は、毎回2つのブラシしか存在しないことを明確にする必要があります.横にペンを置くか、縦にペンを置くか.

縦ブラシは「切断」の問題はなく、横ブラシは存在する.

思考過程.
step1
横方向切断の問題があるため、連続横区間処理が必要である可能性があることを意味するため、まず再帰を用いて、各層再帰で現在の木材の最低高さを見つけ、この高さよりも大きい木材が次の層に入って再帰し、最低高さよりも連続的に大きい木材が同じ再帰であることを考えるべきである.テーマから与えられたデータ範囲を見ると、最大5000枚の板であれば、各層の再帰が1枚の木材しか少なくなければ、再帰深さも5000を超えることはなく、gccやg++コンパイラにとって許容できる.
Step 2(コードを見てからこの部分を見ることをお勧めします)
本当に法則が思いつかないので、すべての木材を縦にブラシして、すべての木材と横にブラシをかけて比較すると、誰が小さいかが結果になります.しかし問題として、横向きブラシが切れてしまうという問題があり、一度に横向きに全部ブラシをかけることができず、横向きブラシが終わった後、後ろに縦にブラシをかける回数が少なくなる可能性がある.では、再帰的に、私たちはすべての木材の中で最小の高さを探して、最小の高さは横塗りの壁に必要な回数で、それから残りの壁塗りの回数を加えて、横塗りの壁の回数です.次に,最小高さを境界線として,複数の連続したより高い高さの新しい壁を得,これらのサブ問題について上記と同様の処理を行った.
最終的な考え方.
最後の最小回数は必ず全ての縦塗り壁に等しいものより小さく、横塗り壁の場合、0-最小高さを全ての縦塗り壁より小さくすることができる(横塗りの範囲はもっと高くなく、もっと小さくすることもできず、最小高さに等しいものだけが最適解を得ることができ、なぜ、よく証明されるのか)ため、このような状況を議論する必要がある.これで分治の考えができた.ブラシが終わった後、私たちは「ベースライン」を最小高さの上に移動して、このようにして複数の連続的な規模のもっと小さい新しい壁を得ました.これは望みの問題と同じサブ問題で、私たちはサブ問題の最適解を求める必要があります.望みの問題の最適解はサブ問題の最適解(最適サブ構造)を含んでいます.現在の状態は、横ブラシと縦ブラシの両方の場合の最小値によって決定される.だからこの問題には貪欲、分治、動態計画思想が入っている.
コード#コード#

#include 
#include 
#include 
using namespace std;
//max re-deep is 5000,is ok 
int dfs(int* a,int l,int r,int h)
{
    if(l == r) 
        return 1;
    int min_h = *min_element(a+l,a+r+1);
    int res = min_h - h;
    for(int i=l;i<=r;i++)
    {
        if(a[i] > min_h)
        {
            int j = i;
            while(j < r && a[j+1] > min_h ) j++;
            res += dfs(a,i,j,min_h);
            i = j;
        }
    }
    return min(res,r-l+1);
}

int main()
{
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0;i<n;i++)
    {
        cin >> arr[i];
    }
    cout << dfs(arr,0,n-1,0);
    return 0;
}