Algoogle

Algorithm for Programming Contest

PKU 3276 Face The Right Way

Category: PKU Tag: dp

Face The Right Way

問題概要


N匹の牛が順に並んでいて, 前か後ろを向いている.
長さKを決めて, その長さの区間の牛をいっぺんに向きを反転させることができる.
全て前を向かせるときの反転の回数の最小とそのときのKを求めよ.

解法


左側から見ていって, 区間の一番左側の牛を前に向かせるようにしていく
そのとき最後の区間の残りが全部前を向いていればよい.
愚直にやるとO(N^3)だが区間の現在見ている牛を反転しているかどうかを, それより前までの区間から影響のある場所を反転したかどうかをxorとってやれば現在の位置が反転されているかがわかる.
あとはKを全て試せば良い.

コード


(3276.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <cstring>

using namespace std;

const int inf = 1e9;
int N;
bool tile[5010], flip[5010];

void solve(){
    int M = inf, K;
    for(int k = 1; k <= N; k++){
        int m = 0;
        bool sum = 0;
        memset(flip, 0, sizeof(flip));
        for(int i = 0; i <= N-k; i++){
            flip[i] = !(sum^tile[i]);
            m += flip[i];
            sum ^= flip[i];
            if(i >= k-1) sum ^= flip[i-k+1];
        }
        for(int i = N-k+1; i < N; i++){
            if(!(sum^tile[i])) m = inf;
            sum ^= flip[i-k+1];
        }
        if(M > m){
            M = m;
            K = k;
        }
    }
    printf("%d %d\n", K, M);
}

int main(){
    scanf("%d\n", &N);
    for(int i = 0; i < N; i++){
        char c; scanf("%c\n", &c);
        tile[i] = (c == 'F');
    }
    solve();
    return 0;
}

Comments