首页 > 代码库 > poj3276 Face The Right Way

poj3276 Face The Right Way

原题链接:poj3276 Face The Right Way

题意:N头牛有的头向前有的头向后(F代表向前,B代表向后),每次只能让连续的K头牛方向反转,求:让所有的牛头向前,用的最少次数M和对应的最小K

输入:N 及每头牛的状态

输出:K M

 

//思路:从最左边开始找是B,就需要反转i到i+k-1的位置(把第i项先反转为F) 
//一直找到i=n-k+1处,之后判断从n-k+2到n是否都为F,注意不要真的去修改
//尺取法用sum记录第i-k+1项到第i项个反转次数,以此来决定当前的是否要修改
//i-K+1表示第i项起为第1项向前推进K项的位置,如i=3,K=3推进后是位置是1(位置从0开始) 
//i+K-1表示第i项起为第1项向后推进K项的位置,如i=0,K=3推进后是位置是2(位置从0开始) 
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_N = 5005;
int N;
int dir[MAX_N]; //牛的方向:0:F, 1:B 
int f[MAX_N];    //区间[i, i+K-1]内的K头牛是否进行了反转(反转为1,否则为0) 
//固定K,求对应的最小操作的回数
//无解的话则返回-1 
int calc(int K){
    memset(f, 0, sizeof(f));
    int i, res = 0, sum = 0;    //sum是f的和 
    for(i = 0;i + K <= N;i ++){    //计算区间[i, i+K-1] 
        if((dir[i] + sum) & 1){    //前端的牛面朝后方,本来的状态加上反转的次数的奇偶性判断 
            res ++;
            f[i] = 1;
            sum += f[i];    //i前端的牛反转的次数 
        }
        if(i - K + 1 >= 0){    //尺取法保留区间[i-K+2, i+1]内的反转次数和,以此来判断第i+1项是否需要再反转
            sum -= f[i - K + 1];
        }
    }
    for(;i < N;i ++){    //检查剩下的牛是否有面朝后方的情况 
        if((dir[i] + sum) & 1){    //无解 
            return -1;
        }
        if(i - K + 1 >= 0){
            sum -= f[i - K + 1];
        }
    }
    return res;    //返回反转次数 
} 
int main(){
    char c;
    scanf("%d", &N);
    for(int i = 0;i < N;i ++){
        scanf(" %c", &c);
        dir[i] = (c == F ? 0 : 1);
    }
    int K, M = N;
    for(int k = 1;k <= N;k ++){    //k从1到N搜索答案 
        int m = calc(k);    //对每个k计算出最小反转次数 
        if(m >= 0 && M > m){    //找到最小的反转次数M和个数K 
            M = m;
            K = k;
        }
    }
    printf("%d %d\n", K, M);
    return 0;
}

 

poj3276 Face The Right Way