#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#define n 20
using namespace std;
int A[30][30],a[30],x[30],var,ans,var0;
void swap(int &a,int &b)
{
    int tmp=a;
    a=b;
    b=tmp;
}
int gaos(int r,int c)
{
    int i=1,j=1,l,k,id;
    while(i<=r&&j<=c)
    {
        id=i;
        for(l=i+1; l<=r; l++)
        {
            if(A[l][j]>A[id][j])id=l;
        }
        if(A[id][j])
        {
            for(l=j; l<=c+1; l++)swap(A[id][l],A[i][l]);
            for(l=i+1; l<=r; l++)
            {
                if(A[l][j])
                {
                    for(k=j; k<=c+1; k++)A[l][k]=A[l][k]^A[i][k];
                }
            }
            i++;
        }
        j++;
    }
    var=i;
    if(var<i+1)
    {

        return 0;
    }
    memset(x,0,sizeof(x));
    for(i=c; i>=1; i--)
    {
        for(j=i+1; j<=r; j++)A[i][c+1]^=(A[i][j]&&x[j]);
        x[i]=A[i][c+1];
    }
    int ans=0;
    for(i=1; i<=c; i++)if(x[i])ans++;
    return ans;
}
int cp[30][30],cpx[30];
void dfs(int var)
{
    int i,j;
    if(var==n+1)
    {
        for(i=1; i<=n; i++)
        {
            cpx[i]=x[i];
            for(j=1; j<=n+1; j++)
            {
                cp[i][j]=A[i][j];
            }
        }
        for(i=var0-1; i>=1; i--)
        {
            for(j=i+1; j<=n; j++)
            {
                cp[i][n+1]^=(cpx[j]&&cp[i][j]);
            }
            cpx[i]=cp[i][n+1];
        }
        int tt=0;
        for(i=1; i<=n; i++)if(cpx[i])tt++;
        ans=min(ans,tt);
        return;
    }
    x[var]=1;
    dfs(var+1);
    x[var]=0;
    dfs(var+1);
}
int main()
{
    //freopen("in.txt","r",stdin);
    int i,j,xx;
    memset(A,0,sizeof(A));
    for(i=1; i<=n; i++)
    {
        scanf("%d",&xx);
        if(xx)A[i][n+1]=1;
    }
    for(i=1; i<=n; i++)
    {
        A[i][i]=1;
        if(i>1)A[i][i-1]=1;
        if(i<n)A[i][i+1]=1;
    }
    ans=gaos(n,n);
    if(ans)printf("%d\n",ans);
    else
    {
        ans=50;
        var0=var;
        dfs(var);
        printf("%d\n",ans);
    }
    return 0;
}

• Re:高斯消元+枚举 ～～贴个代码吧 (2) CatLovers 2014-07-23 10:57:32
  • where cow? we can just enumerate the first bow,then the remain bow can be determined through just O(n) time complexity. the total time complexity is just O(n) (6) yygy 2014-07-23 11:04:12