lanqiao oj 小明的宠物袋

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const int N = 12 , M = 35 ;
int a[M][M] ;
int n , m ;
int f[M][1<<N] ;
int row[100100] ;
int t ;
int w[M] ;
int cnt_1(int x){
  int num = 0 ;
  while(x){
    if(x&1) num ++ ;
    x >>= 1 ;
  }
  return num ;
}
int main(){
  cin >> n >> m;
  for(int i = 1 ; i <= n ;i ++){
    int tmp = 0 ;
    for(int j = 1 ; j <= m ; j ++){
      cin >> a[i][j] ;
      tmp |= (a[i][j]<<(j-1)) ;
    }
    w[i] = tmp ;
  }
  for(int i = 0 ; i < 1 << m ; i ++){//判断同一排的合法状态 
    if((i & (i>>1) )==0) row[i] = true ;
    else row[i] = false ;
  }
  
  for(int i = 1 ; i <= n ;i ++){
    for(int j = 0 ; j < 1 << m ; j ++){
      if((w[i] & j) == 0 && (row[j])){
        for(int k = 0 ; k < 1 << m ; k ++){
          if(row[k] && (k&j) == 0&&(w[i-1]&k) == 0)f[i][j] = max(f[i][j] , f[i-1][k]  + cnt_1(j));
        }
      }
    }
  }
  int ans = 0 ;
  for(int i = 0 ; i < 1 << m ; i ++) ans = max(ans,f[n][i]) ;
  cout << ans << endl ;
}