POJ 3276 Face The Right Way——开关问题

POJ 3276 Face The Right Way——开关问题

题意：有n头牛，每头牛向前或向后，现在想让所有牛向前，每次只能反转连续的k（未知）只牛，求最少操作数以及对应的k。

思路：枚举k，对于每一个k，从左向右依次判断，如果当前位置的牛经过前面的反转后向前，那么继续判断下一个，如果向后，那么cnt++，继续判断下一个，判断完后如果整个区间全部是向前的牛，那么用cnt更新结果。

上面思路的复杂度是O(n^3)，我们现在要优化内层循环，即变换牛的朝向的那一层循环，可以用f【i】表示区间【i，i + k - 1】进行了反转（用1和0表示），然后用sum统计当前区间前k个区间的f【】总和，即前k个区间的变化对这个位置的影响，如果sum为奇数，说明这个位置的朝向和输入相反，反之相同。

注意：代码编写过程中存在大量+1-1的问题，应该考虑清楚再写。

#include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 5050;int n, f[maxn];char str[maxn];int main(){ while (scanf("%d", &n) == 1) { for (int i = 0; i < n; i++) { getchar(); scanf("%c", &str[i]); } bool judge = true; for (int i = 0; i < n; i++) { if (str[i] == 'B') { judge = false; break; } } if (judge) { printf("0 0\n"); continue; } int ansk = 0, ansm = INF; for (int k = 1; k <= n; k++) { memset(f, 0, sizeof(f)); int sum = 0, cnt = 0; for (int i = 0; i < n - k + 1; i++) { if ( (sum % 2 == 0 && str[i] == 'F') || (sum % 2 == 1 && str[i] == 'B') ) { f[i] = 0; } else { f[i] = 1; cnt++; } sum += f[i]; if (i + 1 - k >= 0) { sum -= f[i + 1 - k]; } } bool ok = true; for (int i = n - k + 1; i < n; i++) { if ( (sum % 2 == 1 && str[i] == 'F') || (sum % 2 == 0 && str[i] == 'B') ) { ok = false; break; } if (i + 1 - k >= 0) { sum -= f[i + 1 - k]; } } if (ok && ansm > cnt) { ansk = k; ansm = cnt; } } printf("%d %d\n", ansk, ansm); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。