CodeForces 425B Sereja and Table

本文主要是介绍CodeForces 425B Sereja and Table，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

一个充满0和1的矩形  最多将k个数字翻转  问  最少翻转几个数字可以使所有0或1的连通块都是矩形  如果不可能输出-1

思路：

首先  如果确定了一行  那么整个矩形就确定了

因为在最后的状态中  每一行要么与确定的行完全一致  要么完全相反  这才能保证连通块都是矩形

然后  本题k很小  因此可以分类讨论

如果 max(n,m)<=k 那么可以暴力枚举第一行状态  进而计算翻转次数  最多只有2^10种情况

否则 max(n,m)>k  那么至少有一行或者一列是没有被修改的  那么可以枚举哪一行没被修改  再计算翻转次数

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 110int a[N][N];
int n,m,t,tmp,ans,sum;int main()
{int i,j,k;scanf("%d%d%d",&n,&m,&t);for(i=1;i<=n;i++) for(j=1;j<=m;j++) scanf("%d",&a[i][j]);if(n<m){for(i=1;i<=m;i++){for(j=i+1;j<=m;j++) swap(a[i][j],a[j][i]);}swap(n,m);}/*for(i=1;i<=n;i++){for(j=1;j<=m;j++) printf("%d ",a[i][j]);puts("");}*/ans=t+1;if(n<=t){for(i=0;i<(1<<m);i++){sum=0;for(k=1;k<=n;k++){tmp=0;for(j=0;j<m;j++){if(i&(1<<j)){if(!a[k][j+1]) tmp++;}else{if(a[k][j+1]) tmp++;}}sum+=min(tmp,m-tmp);}ans=min(ans,sum);}}else{for(i=1;i<=n;i++){sum=0;for(k=1;k<=n;k++){tmp=0;for(j=1;j<=m;j++){if(a[k][j]!=a[i][j]) tmp++;}sum+=min(tmp,m-tmp);}ans=min(ans,sum);}}if(ans>t) printf("-1\n");else printf("%d\n",ans);return 0;
}

这篇关于CodeForces 425B Sereja and Table的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---