Algoogle

Algorithm for Programming Contest

Codeforces 448C Painting Fence

Category: Codeforces Tag: divide-and-conquer

Painting Fence

問題概要


n個のフェンスが並んであって, それぞれ幅1, 高さがa[i]になっている.
これらをすべて塗りつぶしたい.
連続する縦か横に一気に塗ることができるとき, 最小何回でぬれるか

解法


分割統治する.
区間[l,r)を塗るとき, そのなかで最小の高さ以下の部分は横に一気に塗りつぶせる.
そこでその高さの部分で分割していく.
分割された左右の結果と最小の高さの和(つまりこの区間で横に塗る回数)と, その区間全てを縦に塗る回数(つまりr-l)の最小がその区間を塗るのにかかる最小回数.
また分割していくとき, 下の部分は塗ってあると仮定するのでその高さを床にする.
あとはコードを見ればわかるはず.

ちなみに今回は毎回区間を舐めて最小の高さを求めているのでになるが, Segment Treeを用いればに落とせる

コード


(448C.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)

int n, a[5010];

int rec(int l, int r, int f){
    if(l >= r) return 0;
    int m = l;
    repi(i,l,r) if(a[m] > a[i]) m = i;
    return min(r-l,a[m]-f+rec(l,m,a[m])+rec(m+1,r,a[m]));
}

int main(){
    cin >> n;
    rep(i,n) cin >> a[i];
    cout << rec(0,n+1,0) << endl;
    return 0;
}

Comments