解法同poj 1185
只有判断冲突的情况不同
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <iomanip> #include <queue> #include <vector> #include <set> #include <map> typedef long long LL; #define inf 0x3f3f3f3f #define P system("pause") using namespace std; #define M 105 int dp[M][180][180],m,n; int mp[M][15]; int s[180],ssize,cur[M],num[180]; bool isok(int status,int k) { if(cur[k]&status) return 0; return 1; } int count(int x) { int s=0; while(x) { if(x&1) s++; x>>=1; } return s; } int judge(int x) { if(x&(x<<2))return 0; if(x&(x>>2))return 0; return 1; } void init() { int tot=1<<m; ssize=0; for(int i=0;i<tot;i++) { if(judge(i)) s[ssize++]=i; } } int main() { int i,j,k,t; while(scanf("%d%d",&n,&m)!=EOF) { init(); for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&mp[i][j]); for(i=1;i<=n;i++) { cur[i]=0; for(j=1;j<=m;j++) { if(mp[i][j]==0) cur[i]+=(1<<(j-1)); } } memset(dp,-1,sizeof(dp)); for(i=0;i<ssize;i++) { num[i]=count(s[i]); if(isok(s[i],1)){ dp[1][0][i]=num[i]; } } for(i=2;i<=n;i++) { for(t=0;t<ssize;t++) { if(!isok(s[t],i))continue; for(k=0;k<ssize;k++) { if(((s[k]<<1)&s[t]) || ((s[k]>>1)&s[t]) )continue; for(j=0;j<ssize;j++) { if(s[t]&s[j])continue; if(((s[j]<<1)&s[k]) || ((s[j]>>1)&s[k]) )continue; if(dp[i-1][j][k]==-1)continue; dp[i][k][t]=max(dp[i][k][t],dp[i-1][j][k]+num[t]); } } } } int ans=0; for(i=1;i<=n;i++) for(j=0;j<ssize;j++) for(k=0;k<ssize;k++) ans=max(ans,dp[i][j][k]); printf("%d\n",ans); } return 0; }