首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。