POJ 3276 Face The Right Way
题目大意：
一N头站成一排，有的面向前站，也有的面向后站。你有一种可以且只能反转连续的K头牛的朝向的机器。少于K头牛无法使用此机器。你需要让所有的牛都面朝前站。求一个最小的K，使得反转的次数M最少。
输入：
第一行， N 接下来2~N+1 行， 每行一个字符 ‘B’ 或者 ‘F’ 表示这头牛面朝前还是朝后。
输出：
K M
题解：
对于一个固定的k，求翻转所需要的最少次数，最朴素的有一个 O(n2) 的算法： 首先要明确，反转的次序是不重要的，对同一个区间反转两次和不反转的效果是一样的。 我们数组a[] 存所有牛的状态， 0表示面朝前方，1表示面朝后方。 对于第1头牛，只有 (1,2,...,k) 这一个反转可以影响它的状态， 所以如果第一头牛是’B’，则必须执行翻转 (1,2,...,k) ，改变 (1,2,...,k) 这些牛的状态。这时候，第2头牛的状态只与反转 (2,3,...,k+1) 有关。这就把问题规模为 n 的为题转化为规模为 n−1 的问题。利用此贪心算法，枚举前 n−k+1 头牛， 最后看下第 n−k+2 n 头牛的状态是否全都朝向前方，就可以判断当前K是否可行， 并给出解。这个算法在Problem A. Oversized Pancake Flipper中写过。
需要求最小的K， 只需要把K 从1 到 N枚举一遍。这样算法的总体复杂度为 O(n3) 。应该是不能接受的。
好在前面的 O(n2) 的算法可以优化为一个 O(n) 的算法： 对于第 i 头牛，它的当前的状态与第 i−k 1 i−1 头牛的位置是否反转过有关。这里在第 i−k+1 头牛处反转，意味着 (i−k+1,...i) 这些牛的状态都要改变。对于第 i 头牛，只需要关注在i−k 1 i−1 处反转的次数sum。 第i头牛的状态为a[i]，那么第i头牛的当前状态就为(sum + a[i] ) % 2， 是奇数则表示面朝后方，需要反转，偶数则表示面朝前方，不需要反转。 这样只需要维护一个sum值 和 记录以哪些牛为起始位置反转过的数组f[]。 sumi+1=sumi+f[i]−f[i−k+1]
代码
#include <iostream> #include <cstring> #define MAXN 5010 #define INF 0x3f3f3f3f using namespace std; int n; int a[MAXN], f[MAXN]; int solve(int k) { memset(f, 0, sizeof(f)); int ans = 0, sum = 0; for (int i = 0; i < n-k+1; i++) { if ((a[i] + sum) % 2 != 0) { ans++; f[i] = 1; } sum += f[i]; if (i+1-k >= 0) { sum -= f[i+1-k]; } } //判断当前k是否可行 bool flag = false; for (int i = n-k+1; i < n; i++) { if ((a[i] + sum) % 2 != 0) { flag = true; break; } if (i+1-k >= 0) { sum -= f[i+1-k]; } } return flag ? INF : ans; } int main() { ios::sync_with_stdio(false); cin >> n; char c; for (int i = 0; i < n; i++) { cin >> c; a[i] = (c == 'B' ? 1 : 0); } int K = 0; int M = INF; //枚举n次 for (int i = 1; i <= n; i++) { int tmp = solve(i); if (tmp < M) { M = tmp; K = i; } } cout << K << " " << M << endl; return 0; }