Codeforces 425B

点击打开题目链接　

题意：给定一个ｎ×ｍ的０，１矩阵，做多可以对矩阵做ｋ次变换，每次变换只可以将矩阵的某一个元素由０变成１，或从１变成０。

求最小的变换次数使得得到的矩阵满足：每一个连通块都是一个“实心”矩形。

要想清楚的就是最终的矩阵一定是这样的：　

0１０...

1 0 1 ...

0 1 0 ...　这样的０，１交替的矩阵，这里０，１分别表示一个矩形。

如果　n > k，　那么肯定又一行是没有改变的（为什么？想一想），那么只需要枚举这没有改变的一行，其他行要么和他完全相同，要么完全不同（为什么？想一想）。并且任何两行之间没有任何的其他依赖关系，所以只需要取变换次数最少的一种。

如果　ｎ< k, 　那么可以枚举第一列最后的情况，也就是２^ n，这里ｎ< k,　而且ｋ<10。　然后和上面一样就可以了。

附上代码：

 /*************************************************************************

     > File Name: 425B.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年04月30日 星期三 21时44分14秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define MAX_N (100 + 5)

 #define min(x, y) ((x) < (y) ? (x) : (y))

 int n, m, k;

 int a[MAX_N][MAX_N];

 int

 main(void) {

         scanf("%d %d %d", &n, &m, &k);

         for (int i = ; i < n; i++)

                 for (int j = ; j < m; j++)

                         scanf("%d", &a[i][j]);

         int ans = ;

         if (k < n) {

                 for (int i = ; i < n; i++) {

                         int tmp = ;

                         for (int j = ; j < n; j++) if (i != j) {

                                 int cnt1 = , cnt2 = ;

                                 for (int t = ; t < m; t++) {

                                         if (a[j][t] == a[i][t]) {

                                                 cnt1++;

                                         } else {

                                                 cnt2++;

                                         }

                                 }

                                 tmp += min(cnt1, cnt2);

                         }

                         if (tmp < ans) {

                                 ans = tmp;

                         }

                 }

         } else {

                 for (int i = ; i < (<<n); i++) {

                         int tmp = , b[MAX_N];

                         for (int j = ; j < n; j++) {

                                 if (i & (<<j)) {

                                         if (a[j][] == ) {

                                                 b[j] = ;

                                                 tmp++;

                                         } else {

                                                 b[j] = ;

                                         }

                                 } else {

                                         if (a[j][] == ) {

                                                 b[j] = ;

                                                 tmp++;

                                         } else {

                                                 b[j] = ;

                                         }

                                 }

                         }

                         for (int j = ; j < m; j++) {

                                 int cnt1 = , cnt2 = ;

                                 for (int t = ; t < n; t++) {

                                         if (a[t][j] == b[t]) {

                                                 cnt1++;

                                         } else {

                                                 cnt2++;

                                         }

                                 }

                                 tmp += min(cnt1, cnt2);

                         }

                         if (tmp < ans) {

                                 ans = tmp;

                         }

                 }

         }

         if (ans > k) {

                 puts("-1");

         } else {

                 printf("%d\n", ans);

         }

         return ;

 }

巴特西

Codeforces 425B

最新文章

热门文章