POJ 3276 Face the Right Way

Description

N头牛排成一列，有面朝前（F）的、面朝后（B）的，有一台机器能让连续K头牛翻转方向，

求让所有牛面朝前的最少操作次数M，及此时对应的K；

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

Idea

翻转问题的特点：

1. 若确定了翻转方案，交换翻转顺序对结果无影响
2. 对同一区间：要么不反转，要么只翻转一次。多次翻转是多余的。

首先对最左边的牛进行判断，如果这头牛已经朝前方了，那么以这头牛为开始的区间就不需要在进行反转。

如果这头牛朝后面，那么对应的以该牛为开始的区间就反转。不停重复以上步骤即可。

但是如果反转牛时对每一头牛都进行反转操作的话时间复杂度就成了O(n^3)，肯定超时，所以必须在反转操作上进行优化。

f[i]:=区间[i,i+k-1]进行了反转的话为1,否则的话为0

这样在考虑第i头牛时候，如果sum(f[i-k+1]+…+f[i-1)为奇数的话，则与开始方向相反，否则相同。这样就将反转操作的复杂度将为常数，整个算法复杂度将为O(n^2)

Code

#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n;
bool dir[5005];///0 is face. 1 is back.
bool f[5005];
///0 is that the interval which refers to [i, i + k - 1] wasn't flip.

int cal(int k)
{
    memset(f, 0, sizeof(f));
    int res = 0, sum = 0;
    for(int i = 0; i + k <= n; ++i)
    {
        if((dir[i] + sum) & 1)
            res++, f[i] = 1;

        ///update the sum
        sum += f[i];
        if(i - k + 1 >= 0)///the first
            sum -= f[i - k + 1];
    }

    ///check the remain
    for(int i = n - k + 1; i < n; ++i)
    {
        if((dir[i] + sum) & 1)
            return -1;
        if(i - k + 1 >= 0)
            sum -= f[i - k + 1];
    }

    return res;
}

int main()
{
    scanf("%d", &n);
    getchar();
    char s[5005];
    for(int i = 0; i < n; ++i)
        s[i] = getchar(), getchar();

    memset(dir, 0, sizeof(dir));
    for(int i = 0; i < n; ++i)
        if(s[i] == 'B')
            dir[i] = 1;

    int ans_k = 1, ans_m = n;
    for(int k = 1; k <= n; ++k)
    {
        int m = cal(k);
        if(m >= 0 && ans_m > m)
            ans_m = m, ans_k = k;
    }
    cout << ans_k << ' ' << ans_m << '\n';
    return 0;
}