painting fence - 分治 - Codeforces 448c

2017-08-02 14:27:18

writer：pprp

題意：

　　• 每塊木闆寬度均為1，高度為h[i]

　　• n塊木闆連接配接為寬度為n的栅欄

　　• 每次可以刷一橫或一豎(上色)

　　• 最少刷多少次可以使得栅欄被全部上色

　　• 1 ≤ n ≤ 5000

算法分析：可以橫着刷，可以豎着刷，橫着刷是為了減小豎着刷的次數

　　　　采用分治，每個分治中都取橫着刷和豎着刷兩者的最小值

代碼及說明如下：

#include <iostream>
#include <queue>

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 5010;
int n;
int a[maxn];

//在遞歸算法中不要用n，應該考慮的是在每個部分，而不能隻是在第一個遞歸中的角标
int dfs(int l,int r)
{
    int MIN = INF;
    int cnt = 0;

    //找到所有木闆中最短的那個
    for(int i = l ; i <= r; i++)
    {
        MIN = min(MIN, a[i]);
    }

    //将數目加上最短闆長度
    cnt += MIN;

    //所有的木闆減去這個長度
    for(int i = l; i <= r; i++)
    {
        a[i] -= MIN;
    }

    int left = l;

    //  分段遞歸解決問題
    for(int i = l; i <= r; i++)
    {
        if(a[i] == 0)
        {
            cnt +=dfs(left,i-1);
            left = i+1 ;
        }
    }
    
    //最後一段,需要一個判斷
    if(left <= r)
        cnt += dfs(left,r);

    return min(cnt,r-l+1);
}

int main()
{     
    cin >> n;    

    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i];
    }
    
    cout << dfs(1,n) << endl;


    return 0;
}      

代碼改變世界