题意:奶牛有20只碗摆成一排,用鼻子顶某只碗的话,包括左右两只在内的一共三只碗会反向,现在给出碗的初始状态,问至少要用鼻子顶多少次才能使所有碗都朝上。
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int a[30][30], x[30]; int fre[30], index[30], fnum; int equ, var, order, ans; void Debug () { for ( int i = 0; i < equ; i++ ) { for ( int j = 0; j <= var; j++ ) printf("%d ",a[i][j]); printf("\n"); } printf("\n"); } int cal () { int i, j, k, sum; k = var - 1; sum = 0; for ( i = order - 1; i >= 0 && k >= 0; i-- ) { while ( k >= 0 && fre[k] ) sum += x[k--]; if ( k >= 0 ) { x[k] = a[i][var]; for ( j = k + 1; j < var; j++ ) x[k] ^= ( a[i][j] && x[j] ); sum += x[k--]; } } return sum; } void dfs ( int k, int cnt ) { if ( cnt >= ans ) //剪枝 return; if ( k >= fnum ) { int tmp = cal(); if ( ans > tmp ) ans = tmp; return; } x[index[k]] = 0; dfs ( k + 1, cnt ); x[index[k]] = 1; dfs ( k + 1, cnt + 1 ); } int Gauss () { int i, j, row, col, mr; row = col = fnum = 0; while ( row < equ && col < var ) { mr = row; for ( i = row + 1; i < equ; i++ ) if ( abs(a[i][col]) > abs(a[mr][col]) ) mr = i; if ( mr != row ) for ( j = col; j <= var; j++ ) swap ( a[mr][j], a[row][j] ); if ( a[row][col] == 0 ) { fre[col] = 1; index[fnum++] = col; col++; continue; } for ( i = row + 1; i < equ; i++ ) { if ( a[i][col] == 0 ) continue; for ( j = col + 1; j <= var; j++ ) a[i][j] ^= a[row][j]; } row++; col++; } order = row; ans = 30; dfs ( 0, 0 ); return ans; } int main() { equ = var = 20; memset(a,0,sizeof(a)); for ( int i = 0; i < equ; i++ ) { a[i][i] = 1; if ( i != 0 ) a[i][i-1] = 1; if ( i != equ - 1 ) a[i][i+1] = 1; } for ( int i = 0; i < equ; i++ ) scanf("%d",&a[i][var]); Gauss(); printf("%d\n",ans); return 0; }