竹園論壇

標題: 448C - Painting Fence [打印本頁]

作者: domen111 時間: 2014-7-18 14:24
標題: 448C - Painting Fence
本帖最後由 domen111 於 2014-7-18 14:24 編輯

Codeforces Round #256 (Div. 2) - C . Painting Fence

這題有點難，本來以為要寫不出來了，沒想到在比賽剩下24分鐘的時候解出來了，解出了這一題讓我的排名變成158，rating變1721(Candidate Master)，也就是有資格比Div.1了

，下次比賽準備被Div.1電了。

這題有一點DP或divide and conquer的概念，用遞迴就可以輕鬆解出，程式碼短短38行，不過要想很久。

下面是一筆測資的範例:

遞迴第一次執行紅色部分，試看看橫向塗色或直向比較好。
1. 若為橫向塗色，紅色有兩列，所以答案為 2+(塗上面部分的答案) ，所以就呼叫遞迴，執行黃色和綠色的部分就可以了。
2. 若為直向塗色，總共有10個直行，所以答案就是10。
return 1或2答案較小的那一筆

不過如果認真想會遇到一個問題: 會不會遞迴下去的部分會影響到上一層的結果呢? 這個概念和DP很像，如果會影響到的話，這個演算法就是錯的。
如果上層迴圈呼叫到目前迴圈，上層迴圈必定是橫向塗色，如果目前迴圈為直向塗色，將會塗到下層迴圈塗過的區域，那這樣會不會讓下層迴圈的答案變小呢? 答案是不會的，因為目前迴圈的塗色範圍不可能包含上層迴圈塗色範圍的整個橫列(否則就不會被分成兩次迴圈了)。

My AC code:

[C++] 純文本查看 復制代碼

#include<iostream>

#include<algorithm>

using namespace std;

int n;

int a[6000];

int sol(int l,int r)

{

    //horizontal strokes

    int ans=INT_MAX;

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

        ans=min(ans,a);

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

        if(a!=0)

            a-=ans;

    int tl=-1,tr=0;

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

    {

        if(i!=r+1 && a!=0)

        {

            if(tl==-1) tl=i;

            tr=i;

        }

        else if(tl!=-1)

        {

            ans+=sol(tl,tr);

            tl=-1;

        }

    }

    

    return min(ans,r-l+1);

}

int main()

{

    cin>>n;

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

        cin>>a;

    cout<<sol(0,n-1);

}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)