首页 > 代码库 > codeforces 425B Sereja and Table（状态压缩，也可以数组模拟）
codeforces 425B Sereja and Table（状态压缩，也可以数组模拟）
题目
给出一个n*m的01矩阵, 让你最多改变k个里面的值(0变1,1变0)， 使得0、1的连通分量是矩阵。输出最少步数
1 ≤ n, m ≤ 100; 1 ≤ k ≤ 10
题解：
如果01连通分量是矩形，
那么矩形一定是这样的：
0101010
1010101
0101010
1010101
(上面的01代表子矩阵块)。
也就是每一行要么是相同，要么是相反的。
如果n>k, 肯定有一行是不能改变的，那么枚举这一行，然后其余的要么变相同，要么变相反，看最少的步数。
如果n<k ,那么可以枚举第一列的状态(2^k), 然后其余列变成和第一列相同或者相反。
以上引用自：http://www.cnblogs.com/kuangbin/p/3702113.html
//我不知道我这种模拟算不算是状态压缩
#include <cstdio>#include<iostream>#include <cstring>#include <algorithm>#include<vector>using namespace std;int k,n,m;int a[110][110];int min(int x,int y){ if(x<y)return x; return y;}int meijuh(){ int minn=210000000; for(int i=0;i<k+1;i++) { int ans=0; for(int ii=0;ii<n;ii++) { if(i!=ii) { int sa=0,di=0; for(int j=0;j<m;j++) { if(a[i][j]==a[ii][j]) sa++; else di++; } ans+=min(sa,di); } } minn=min(minn,ans); } return minn;}int meijul(){ int er[2048][11]; for(int i=0;i<2048;i++)er[i][0]=i&1; for(int i=0;i<1024;i++)for(int j=0;j<2;j++)er[i*2+j][1]=i&1; for(int i=0;i<512;i++)for(int j=0;j<4;j++)er[i*4+j][2]=i&1; for(int i=0;i<256;i++)for(int j=0;j<8;j++)er[i*8+j][3]=i&1; for(int i=0;i<128;i++)for(int j=0;j<16;j++)er[i*16+j][4]=i&1; for(int i=0;i<64;i++)for(int j=0;j<32;j++)er[i*32+j][5]=i&1; for(int i=0;i<32;i++)for(int j=0;j<64;j++)er[i*64+j][6]=i&1; for(int i=0;i<16;i++)for(int j=0;j<128;j++)er[i*128+j][7]=i&1; for(int i=0;i<8;i++)for(int j=0;j<256;j++)er[i*256+j][8]=i&1; for(int i=0;i<4;i++)for(int j=0;j<512;j++)er[i*512+j][9]=i&1; for(int i=0;i<2;i++)for(int j=0;j<1024;j++)er[i*1024+j][10]=i&1; int minn=210000000; for(int i=0;i<(1<<n);i++) { int ans=0; for(int j=0;j<m;j++) { int sa=0,di=0; for(int ii=0;ii<n;ii++) { if(er[i][ii]==a[ii][j]) sa++; else di++; } ans=ans+min(sa,di); } minn=min(minn,ans); } return minn;}int main() { cin >>n>>m>>k; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >>a[i][j]; int minn=210000000; if(n>k) { minn = meijuh(); } else { minn=meijul(); } if(minn<=k) cout << minn<<endl; else cout <<-1<<endl; return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。