小明的宠物袋 状态压缩dp

#include <bits/stdc++.h>

using namespace std;

const int N=32;

const int M=15;

int dp[N][1<<M];

int rows[N];

bool valid[1<<M];

int cnt_1(int x)

{

int cnt=0;

while(x)

{

if(x&1)cnt++;

x=x>>1;

}

return cnt;

}

int main()

{

int n,m;

cin>>n>>m;

int upper_limit=(1<<m)-1;

for(int i=1;i<=n;i++)

{

for(int j=1;j<=m;j++)

{

int tmp;

cin>>tmp;

if(tmp)rows[i]|=1<<(j-1);

}

}

for(int i=0;i<=upper_limit;i++)

{

if((i&(i>>1))==0)valid[i]=true;

else valid[i]=false;

}

for(int i=1;i<=n;i++)

{

for(int j=0;j<=upper_limit;j++)

{

if((rows[i]&j)==0&&valid[j])

{

for(int k=0;k<=upper_limit;k++)

{

if((j&k)==0&&valid[k])

{

dp[i][j]=max(dp[i][j],dp[i-1][k]+cnt_1(j));

}

}

}

}

}

int ans=0;

for(int i=0;i<=upper_limit;i++)

{

ans=max(ans,dp[n][i]);

}

cout<<ans<<endl;

return 0;

}