POJ3185 The Water Bowls 反转(开关)

Description

The cows have a line of 20 water bowls from which they drink. The bowls can be either right-side-up (properly oriented to serve refreshing cool water) or upside-down (a position which holds no water). They want all 20 water bowls to be right-side-up and thus
use their wide snouts to flip bowls.

Their snouts, though, are so wide that they flip not only one bowl but also the bowls on either side of that bowl (a total of three or -- in the case of either end bowl -- two bowls).

Given the initial state of the bowls (1=undrinkable, 0=drinkable -- it even looks like a bowl), what is the minimum number of bowl flips necessary to turn all the bowls right-side-up?

Input

Line 1: A single line with 20 space-separated integers

Output

Line 1: The minimum number of bowl flips necessary to flip all the bowls right-side-up (i.e., to 0). For the inputs given, it will always be possible to find some combination of flips that will manipulate the bowls to 20 0‘s.

Sample Input

0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0

Sample Output

3

Hint

Explanation of the sample:

Flip bowls 4, 9, and 11 to make them all drinkable:

0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [initial state]

0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 4]

0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 [after flipping bowl 9]

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [after flipping bowl 11]

这题属于反转(开关)类型的题,典型的特征就是:

1,反转的先后顺序是不重要的;

2,主动对一个开关进行2次或2次以上的反转是多余的。

这题,如果条件是每次必须反转3个碗的话,那么就很简单,先考虑最左端的碗,如果碗朝下,那么这个碗必须反转,同时带动后面两个碗一起反转,这样的话问题的规模就减少了一个,然后重复此方法判断。

但是条件是在两端可以出现同时只反转两个碗的情况,这时候只要先枚举一下两端反转两个碗的所有情况,然后就可以把它当成每次必须反转3个碗进行处理就可以了。

#include <stdio.h>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <stack>
#include <map>

using namespace std;

int main()
{
#ifdef _DEBUG
	freopen("e:\\in.txt", "r", stdin);
#endif
	int side[21];
	int side1[21];
	for (int i = 0; i < 20; i ++)
	{
		scanf("%d", &side[i]);
	}
	int minCount = 50;
	for (int i = 0; i < 4;i++)
	{
		int count1 = 0;
		memcpy(side1, side, sizeof(side));
		if (i == 1)
		{
			side1[0]++;
			side1[1]++;
			count1++;
		}
		else if (i == 2)
		{
			side1[18]++;
			side1[19]++;
			count1++;
		}
		else if (i == 3)
		{
			side1[0]++;
			side1[1]++;
			side1[18]++;
			side1[19]++;
			count1++;
			count1++;
		}
		for (int i = 0; i <= 17; i++)
		{
			if (side1[i] & 1)
			{
				side1[i] ++;
				side1[i + 1]++;
				side1[i + 2]++;
				count1++;
			}
		}
		if (!(side1[1] & 1 || side1[18] & 1 || side1[19] & 1))
		{
			if (minCount > count1)
			{
				minCount = count1;
			}
		}
	}
	printf("%d\n", minCount);
	return 1;
}
时间: 07-20

POJ3185 The Water Bowls 反转(开关)的相关文章

[Gauss]POJ3185 The Water Bowls

题意:反正就是要给的一串01的变成全0 能影响自己和左右 最少需要几步 01方程组 异或解 1 int a[300][300]; // 增广矩阵 2 int x[300]; // 解 3 int free_x[300]; // 标记是否为自由未知量 4 5 int n; 6 void debug() 7 { 8 for(int i=0;i<n*n;i++) 9 { 10 for(int j=0;j<n*n;j++) 11 printf("%d ", a[i][j]); 12

POJ 3185 The Water Bowls(高斯消元法,枚举自由变元)

题目: The Water Bowls Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5013   Accepted: 1960 Description The cows have a line of 20 water bowls from which they drink. The bowls can be either right-side-up (properly oriented to serve refresh

poj 3185 The Water Bowls(高斯消元)

The Water Bowls Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 4352   Accepted: 1721 Description The cows have a line of 20 water bowls from which they drink. The bowls can be either right-side-up (properly oriented to serve refreshing

poj3185--The Water Bowls(高斯消元问题3)

The Water Bowls Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 4623   Accepted: 1812 Description The cows have a line of 20 water bowls from which they drink. The bowls can be either right-side-up (properly oriented to serve refreshing

The Water Bowls [POJ3185] [开关问题]

题意 一串长度为20的0,1数列,每次翻转i,会影响i-1,i+1,也被翻转,最少翻转成0的步骤数是多少? Sample Input 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 Sample Output 3 分析 这一道开关问题和POJ3276很类似,但是那个是有固定长度的,我们可以看做是一个点向后的一个区间进行翻转,就不会对前面产生影响. 这道题就不一样,会影响前面的,那我们就看做是i为作用点,i+1,i+2为附带效应点,就可以转换成上面那种类型了.只是要

Greedy:The Water Bowls(POJ 3185)

水池 题目大意:给定一个20的数组,全都是0和1,可以翻一个数改变成另一个数(0或者1),但是其左右两边的数都会跟着变为原来的相反数,问你怎么用最小的操作数使全部数变成0 这一题的:满足 1:翻转次序不改变结果 2.  从特定次序翻转以后左侧的元素不会再改变 其实就是3276的变形,只是他这次固定变三个数,而且是一前一后,我们把方向dir的查看往前挪一个数就好了,但是这样我们就不能知道第一个数是否需要翻转,所以我们分两种情况来讨论就好了 一开始我想着像3276那样枚举,可是1<<20次实在是太

挑战程序竞赛 反转开关 poj3276

这个我其实也没有看太懂它的证明过程. 1.若某一个位置被翻转了n次,则其实际上被翻转了n%2次. 2.分析易知翻转的顺序并不影响最终结果. 3.现在我们着眼于第1个位置,可知若要将第1个位置进行翻转只有翻转它自己,因为没有其他位置的翻转会引起它的翻转. 由①可知若第1个位置为1则必须且进行翻转(并将其后2个进行连带翻转)且以后不再进行翻转,因为再进行翻转就一共翻转了2次相当于没翻转. 然后着眼于第2个位置,由于第1个位置不再进行翻转,所以要想翻转第2个位置只有翻转它自己,因为没有其他位置的翻转会

反转 开关问题

首先考虑最左端的牛.包含这头牛的区间只有一个,因此如果这头牛面朝前方,这个区间不反转,面朝后方则反转.以此类推,逐渐缩小问题规模. 用数组j[i]=1代表区间[i,i+K-1]进行了反转  j[i]=0代表不反转. 如果一头牛之前被反转的次数为奇数,则朝向和刚开始相反,为偶数则相同. #include<iostream> #include<memory.h> using namespace std; int N,dir[5005]; int j[5005]; //标记区间[i,i-

POJ 3185 - The Water Bowls

据网上传闻,用高斯消元解?(我就是在学高斯消元的时候看到有拿这个题当练手题的) 但是,看到discuss上有人说根本不用什么高斯消元和搜索,我一想也是--这题显然用贪心啊-- 首先前提:翻转问题,1.每个碗只有主动翻转一次和不主动翻转两种情况:2.主动翻转碗的顺序对结果没有影响. 于是我们的思路是,强制按照从左到右这个顺序翻碗碗, 那么,如果有个bowl[i]是1(并且bowl[1]--bowl[i-1]都已经是0),我们要把他变成0,只能翻bowl[i+1],否则,若是我们翻bowl[i],就