a bit of codeforces: Cool Divide and Conquer

Problem Statement:
448C - Painting Fence

Summary:
Given \(N \leq 5000\) sequences of numbers (fences), you can either:
- (paint horizontally) Substract 1 from the sequence consecutively from one end (may start from the first number, or from the next number after any 0s) to the other end (or when another 0 is encountered, whichever is earlier)
- (paint vertically) Set a number to 0

Given this operations, find the minimum number of operation needed to make all number equal to 0

Solution:
The solution to this problem is damn cool and it fits squarely under the divide and conquer paradigm.
Let S(L, R, H) be the minimum number of operations needed to paint the fences from L to R. H is the portion of the height of the fences that have already been painted.
Firstly, we can paint all fence vertically, that means at worst we need R-L+1 number of operations to pain all fences. Otherwise, we can paint the fence horizontally in hope of having a smaller amount of operations. When we paint the fence horizontally, we want to cover as much fences as possible. Furthermore, we want to horizontally paint until we hit the fence with minimum height, since otherwise we will be wasting operation, call this minimum height minH, hence we need minH - H operations. This leads to the formation of separate segments of uncolored fences, which form a smaller subproblem with exactly the same structure. We recursively process each segments and add up the total of each operation together with the operations incurred previously. Finally, we return whichever is smaller, the number of operations incurred when horizontal painting is used, or when only vertical painting is used.

I've written a code for the solution, which run in \(O(N\lg{N})\) time ( since the relationship \(T(N) \leq T(N/2) + O(N) \) holds ).

int minH(int L, int R){
    int ret = MAXINT;
    for(int i=L;i<=R;++i){
        ret = min(ret, a[i]);
    }
    return ret;
}

int rec(int L, int R, int H){
    int MH = minH(L,R);
    int ret = MH - H;
    int prev, state = 0;
    for(int i=L;i<=R;++i){
        if(a[i] > MH && state == 0){
            prev = i;
            state = 1;
        } else if( a[i] == MH && state  == 1){
            ret += rec(prev, i-1, MH);
            state = 0;
        }
    }
    if(state == 1) ret += rec(prev, R, MH);
    return min(R-L+1, ret);
}