程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3185 The Water Bowls(高斯消元法，枚舉自由變元)

POJ 3185 The Water Bowls(高斯消元法，枚舉自由變元)

編輯：C++入門知識

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 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

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]

Source

USACO 2006 January Bronze

題意：有20個碗，翻轉一個碗會連同翻轉他旁邊的碗，問最少翻幾次可以把碗全部翻到正面。

思路：這道題和POJ1753很像，先用高斯消元法求出自由變元，然後枚舉求出最小值。

代碼：

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define PB push_back
#define MP make_pair

#define REP(i,x,n) for(int i=x;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define FORD(i,h,l) for(int i=(h);i>=(l);--i)
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define RI(X) scanf(%d, &(X))
#define RII(X, Y) scanf(%d%d, &(X), &(Y))
#define RIII(X, Y, Z) scanf(%d%d%d, &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf(%d, &X)
#define DRII(X, Y) int X, Y; scanf(%d%d, &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf(%d%d%d, &X, &Y, &Z)
#define OI(X) printf(%d,X);
#define RS(X) scanf(%s, (X))
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define Swap(a, b) (a ^= b, b ^= a, a ^= b)
#define Dpoint  strcut node{int x,y}
#define cmpd int cmp(const int &a,const int &b){return a>b;}

 /*#ifdef HOME
    freopen(in.txt,r,stdin);
    #endif*/
const int MOD = 1e9+7;
typedef vector VI;
typedef vector VS;
typedef vector VD;
typedef long long LL;
typedef pair PII;
//#define HOME

int Scan()
{
	int res = 0, ch, flag = 0;

	if((ch = getchar()) == '-')				//判斷正負
		flag = 1;

	else if(ch >= '0' && ch <= '9')			//得到完整的數
		res = ch - '0';
	while((ch = getchar()) >= '0' && ch <= '9' )
		res = res * 10 + ch - '0';

	return flag ? -res : res;
}
/*----------------PLEASE-----DO-----NOT-----HACK-----ME--------------------*/


const int MAXN=50;



int a[MAXN][MAXN];//增廣矩陣
int x[MAXN];//解集
int free_x[MAXN];//標記是否是不確定的變元



/*
void Debug(void)
{
    int i, j;
    for (i = 0; i < equ; i++)
    {
        for (j = 0; j < var + 1; j++)
        {
            cout << a[i][j] <<  ;
        }
        cout << endl;
    }
    cout << endl;
}
*/


inline int gcd(int a,int b)
{
    int t;
    while(b!=0)
    {
        t=b;
        b=a%b;
        a=t;
    }
    return a;
}
inline int lcm(int a,int b)
{
    return a/gcd(a,b)*b;//先除後乘防溢出
}

// 高斯消元法解方程組(Gauss-Jordan elimination).(-2表示有浮點數解，但無整數解，
//-1表示無解，0表示唯一解，大於0表示無窮解，並返回自由變元的個數)
//有equ個方程，var個變元。增廣矩陣行數為equ,分別為0到equ-1,列數為var+1,分別為0到var.
int Gauss(int equ,int var)
{
    int i,j,k;
    int max_r;// 當前這列絕對值最大的行.
    int col;//當前處理的列
    int ta,tb;
    int LCM;
    int temp;
    int free_x_num;
    int free_index;

    for(int i=0;i<=var;i++)
    {
        x[i]=0;
        free_x[i]=0;
    }
   free_x_num=0;
    //轉換為階梯陣.
    col=0; // 當前處理的列
    for(k = 0;k < equ && col < var;k++,col++)
    {// 枚舉當前處理的行.
// 找到該col列元素絕對值最大的那行與第k行交換.(為了在除法時減小誤差)
        max_r=k;
        for(i=k+1;iabs(a[max_r][col])) max_r=i;
        }
        if(max_r!=k)
        {// 與第k行交換.
            for(j=k;j=0;j--)
    {
        int temp=a[j][20];
        for(int k=j+1;k<20;k++)
        {
            if(a[j][k])
                temp^=x[k];
        }
        x[j]=temp;
        if(x[j])
            cnt++;
    }
    ans=min(ans,cnt);
}

printf(%d
,ans);



        return 0;
}