448C - Painting Fence

domen111

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[i]);
    for(int i=l;i<=r;i++)
        if(a[i]!=0)
            a[i]-=ans;
    int tl=-1,tr=0;
    for(int i=l;i<=r+1;i++)
    {
        if(i!=r+1 && a[i]!=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[i];
    cout<<sol(0,n-1);
}