CFR 448 C. Painting Fence ( D&C )

Problem - 448C - Codeforces

題意：
給不一定同高度的塔一排。油漆可以橫著刷也可以豎著刷，但橫著刷一次的時候，是不能跨過空的欄位。求最少要刷幾次才能刷好所有塔。

數據範圍：
塔數 1 ≤ N ≤ 1e5
塔高度 1 ≤ H[ i ] ≤ 1e9

解法：
遞迴考慮，最少塗刷次數可以是豎著刷全部，或是橫刷到高度最小的後轉換為同結構子問題。由於每往下遞迴一層便少一個塔且呼叫兩個新的狀態，因此狀態數是 O( N lg N )。

時間 / 空間複雜度：
O( N ^ 2 lg N )
若 RMQ 用適當的資料結構便能 O( N lg ^ 2 N )

int N;
vi A;

void init(){
    cin >> N;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

int dfs( int lb, int rb, int h ){ // [ lb, rb )
    if( lb == rb )
        return 0;
    int mid = lb;
    for( int i = lb + 1; i < rb; ++i )
        if( A[ mid ] > A[ i ] )
            mid = i;
    return min( rb - lb, A[ mid ] - h + dfs( lb, mid, A[ mid ] ) + dfs( mid + 1, rb, A[ mid ] ) );
}

void solve(){
    cout << dfs( 0, N, 0 ) << endl;
}