本文主要是介绍开关问题 POJ 3276 POJ 3279 POJ 1222，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
POJ 3276
题目链接：http://poj.org/problem?id=3276
题意：N个牛 ，B表示朝后， F表示朝前，每次可以选择连续的K个牛反转方向，问如何选择K，使得操作数M最少，K也应尽量小。
参考博客：http://www.cnblogs.com/neopenx/p/4071801.html
①从第一头牛开始，如果朝前，不管了。看下一头牛，如果朝后反转K长度区间.....一直扫到区间结束。
②第一趟结束后，如果不符合要求，继续重复①，直到所有牛都朝前。
这样复杂度是O（n^3)，5000*5000*5000，标准TLE。
其实确定反转次数只需要扫一趟就行了，没有必要来回多趟。O（n^2)就能解决。
它的思路是这样的：
f[i]：区间[i,i+k-1]进行了反转的话为，否则为0。
由上式可知，每一次都可以递推出来。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int N;
int dir[5500]; //0表示朝前，1表示朝后
int f[5500]; //表示区间[i, i + K - 1]是否进行反转
int calc(int K) {memset(f, 0, sizeof(f));int res = 0; //反转几次 int sum = 0; //f的和 int i;for(i = 0; i + K <= N; i++) {//计算区间[i, i + K - 1] if((dir[i] + sum) % 2 != 0) {//该区间最前方的牛面朝后方 res++;f[i] = 1;//表示需要反转 }//递推式 sum += f[i];if(i - K + 1 >= 0) {sum -= f[i - K + 1];}}//检查剩下的牛是否有朝后的，有的话就无解 for(i = N - K + 1; i < N; i++) {if((dir[i] + sum) % 2 != 0) {return -1;}if(i - K + 1 >= 0) { //注意还要更新sum sum -= f[i - K + 1];}}return res;
}
int main() {scanf("%d", &N);getchar();int K = 1, M = N;int i;char tmp;for(i = 0; i < N; i++) {if(tmp = getchar() == 'F') dir[i] = 0;else dir[i] = 1;getchar();}for(i = 1; i <= N; i++) {int m = calc(i);if(m >= 0 && M > m) {M = m;K = i;}}printf("%d %d\n", K, M);return 0;
}POJ 3279 （关灯问题）
题目链接：http://poj.org/problem?id=3279
题意：一个m*n的01矩阵，每次点击(x,y)，则(x,y)的上下左右以及本身就会反转，问把矩阵变成全0的，最小需要点击多少步。
挑战程序设计上看到的，应该是比较经典的题目，做法就是枚举吧，不过是效率比较高，特别巧妙地枚举。也是第一次学到了用2进制去表示集合。
做法具体来说就是枚举第一行，然后根据第一行往下推到最后，比较结果找出最小值即可。
详见代码。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int dx[5] = {-1, 0, 0, 0, 1}; //枚举一个点的相邻4点及其本身
const int dy[5] = {0, -1, 0, 1, 0};
int M, N;
//tilt为原始棋盘，ans为最小结果，flip记录中间结果
int tilt[20][20], ans[20][20], flip[20][20];
//此函数用来查询（x，y）点的颜色，0白1黑
int get(int x, int y) { int c = tilt[x][y];int i;for(i = 0; i < 5; i++) {int tx = x + dx[i];int ty = y + dy[i];if(tx >= 0 && tx < M && ty >= 0 && ty < N)c += flip[tx][ty]; //加上被翻过多少次，有很巧妙的关系 }return c % 2;
}int calc() {int i, j;//求第二行开始的反转方法 for(i = 1; i < M; i++) {for(j = 0; j < N; j++) {if(get(i - 1, j) == 1) {//i - 1, j 是黑色，那么在这一行一定要反转，因为只有这一个机会使其变色 flip[i][j] = 1;}}}//最后一行若有黑的则无解 for(i = 0; i < N; i++) {if(get(M - 1, i) == 1) {return -1;}}//统计反转次数 int res = 0;for(i = 0; i < M; i++) {for(j = 0; j < N; j++) {res += flip[i][j];}}return res;
}
int main() {scanf("%d %d", &M, &N);int i, j;for(i = 0; i < M; i++) {for(j = 0; j < N; j++) {scanf("%d", &tilt[i][j]);}}int res = -1;//按字典序尝试第一行的所有可能性 for(i = 0; i < 1 << N; i++) {memset(flip, 0, sizeof flip);for(j = 0; j < N; j++) {flip[0][N - j - 1] = i >> j & 1; //因为要按字典序枚举，1比0大，所以要倒过来 }int num = calc();if(num >= 0 && (res < 0 || num < res)) { //找出最小值 res = num;memcpy(ans, flip, sizeof(ans));}}if(res < 0) puts("IMPOSSIBLE");else {for(i = 0; i < M; i++) {for(j = 0; j < N; j++) {printf("%d%c", ans[i][j], j + 1 == N ? '\n' : ' ');}}}return 0;
}POJ 1222
题目链接：http://poj.org/problem?id=1222
与上题代码基本相同，棋盘固定了5 * 7
这篇关于开关问题 POJ 3276 POJ 3279 POJ 1222的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
