输入n*m的01矩阵、以及k。
n,m<=100,k<=10
问修改至多k个，使得矩阵内的各连通块（连着的0或1构成连通块）都是矩形，且不含另外的数字（边界为0（1）的矩形内不含1（0）），求最少修改个数。
再次感觉以前见过类似的。。。。完全不会。。。
看了题解再看别人的代码才搞懂。。。。
首先，要知道一个结论，满足题意的矩阵，任意2行（列）的抑或值必须为全0或全1。
然后，分类讨论，
如果可以修改个数k<n，如果有答案，那必然至少有一行是没修改的，枚举不修改的行，统计。
k>=n的时候，必然有n,m<=10，这时候可能每一行都有修改，故枚举标准列的情况，即int i=0;i<(1<<n);++i，统计。
复杂度应该是，max(100^3, 100*10*2^10)=10^6
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 using namespace std; 11 12 #define ll long long 13 #define inf 0x3f3f3f3f 14 #define eps 1e-8 15 16 int a[110][110]; 17 int main(){ 18 int n,m,k; 19 while(~scanf("%d%d%d",&n,&m,&k)){ 20 for(int i=0;i<n;++i)for(int j=0;j<m;++j)scanf("%d",a[i]+j); 21 int ans=k+1; 22 if(k<n){ 23 for(int i=0;i<n;++i){ 24 int tmp=0; 25 for(int j=0;j<n;++j){ 26 int dis=0; 27 for(int k=0;k<m;++k) 28 dis+=(a[i][k]^a[j][k]); 29 tmp+=min(dis,m-dis); 30 } 31 ans=min(ans,tmp); 32 } 33 } 34 else { 35 for(int i=(1<<n)-1;i>=0;--i){ 36 int tmp=0; 37 for(int j=0;j<m;++j){ 38 int dis=0; 39 for(int k=0;k<n;++k) 40 if((i&(1<<k))==(a[k][j]<<k)) 41 dis++; 42 tmp+=min(dis,n-dis); 43 } 44 ans=min(ans,tmp); 45 } 46 } 47 if(ans==k+1)puts("-1"); 48 else printf("%d ",ans); 49 } 50 return 0; 51 }