POJ.3276 Face The Right Way

1.Problem
http://poj.org/problem?id=3276

2.Idea
Flipping method.

3.Source

 #define MAX_N 5000  
 int N;  
 int dir[MAX_N];  
 int f[MAX_N];  
 int calc(int k)  
 {  
      memset(f, 0, sizeof f);  
      int res = 0;  
      int sum = 0;  
      for (int i = 0; i + k <= N; i++) {  
           if ((dir[i] + sum) % 2) {  
                res++;  
                f[i] = 1;  
           }  
           sum += f[i];  
           if (i - k + 1 >= 0) {  
                sum -= f[i - k + 1];  
           }  
      }  
      //residual  
      for (int i = N - k + 1; i < N; i++) {  
           if ((dir[i] + sum) % 2) return -1;  
           if (i - k + 1 >= 0) {  
                sum -= f[i - k + 1];  
           }  
      }  
      return res;  
 }  
 void solve()  
 {  
      int K = 1, M = N;  
      for (int k = 1; k <= N; k++) {  
           int m = calc(k);  
           if (m > 0 && M > m) {  
                M = m;  
                K = k;  
           }  
      }  
      cout << K << " " << M << endl;  
 }  
 int main()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) {  
           char c;  
           cin >> c;  
           if (c == 'B') dir[i] = 1;  
           else dir[i] = 0;  
      }  
      solve();  
      return 0;  
 }