题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4539
题意：中文，不解释
题解：将每一行的状态压缩，然后进行DP，也可以用最大团做。这里我用的DP
1 #include<cstdio> 2 #include<cstring> 3 #define max(a,b) ((a)>(b)?(a):(b)) 4 5 int row[110]; 6 int dp[110][220][220];//dp[i][j][k]表示第i行状态为j,i-1行状态为k时的士兵最大值 7 int s[1<<11];//合法状态 8 int cnt[1<<11];//合法状态中1的个数，即可安排的士兵数 9 10 int getcnt(int x){int c=0;while(x>0)c++,x=x&(x-1);return c;} 11 12 int fuck(int n,int m){ 13 int now=0,i,j,k,l,ans=0; 14 for(i=0;i<(1<<m);i++){ 15 if(i&(i<<2))continue; 16 s[now]=i,cnt[now++]=getcnt(i); 17 } 18 for(i=0;i<now;i++){ 19 if(s[i]&row[0])continue; 20 dp[0][i][0]=cnt[i]; 21 } 22 for(i=1;i<n;i++)for(j=0;j<now;j++){ 23 if(s[j]&row[i])continue; 24 for(k=0;k<now;k++){ 25 if((s[j]&(s[k]>>1))||(s[j]&(s[k]<<1)))continue; 26 for(l=0;l<now;l++){ 27 if(s[j]&s[l])continue; 28 dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+cnt[j]); 29 } 30 } 31 } 32 for(i=0;i<now;i++)for(j=0;j<now;j++)ans=max(ans,dp[n-1][i][j]); 33 return ans; 34 } 35 36 int main(){ 37 int n,m,i,j,x; 38 while(~scanf("%d%d",&n,&m)){ 39 memset(row,0,sizeof(row)); 40 memset(dp,0,sizeof(dp)); 41 for(i=0;i<n;i++)for(j=0;j<m;j++){ 42 scanf("%d",&x); 43 if(!x)row[i]=(row[i]<<1)|1;else row[i]<<=1; 44 } 45 printf("%d ",fuck(n,m)); 46 } 47 return 0; 48 }