一道有趣但不难的题目

lyg_wangyushi

那如果改变列的状态，对应这样的情况该怎么办？

[ 本帖最后由 lyg_wangyushi 于 2008-1-14 14:50 编辑 ]

mathe

任意改变行列的顺序都是可以交换的，交换它们不改变结果。
同样，对于同一行或列改变两次以上也没有意义，改变两次等于不改变。
所以最终我们只需要判断：
某些列需要改变和某些行需要改变。
而所有列是否改变总共构成2^9=512种情况，我们对这512种情况都计算最优结果就可以了
对于每种情况，就都只牵涉到行变换，非常简单

lyg_wangyushi

啊，我理解了mathe得意思了，但这样是不是开销太大了一点

lyg_wangyushi

to mathe
希望以后能够多多得到您的指教。真高兴认识您这样一位算法这么强，人品又这么好的人。

mathe

512倍对于现在的计算机应该没有问题。
而对于给定列变换的情况，求解非常简单，只要查看每行朝上多还是朝下多
也就是时间复杂独为O(m*2^n),其中m为行数目，n为列数目

lyg_wangyushi

看样，枚举还真是个好方法。谢谢mathe

lijeki

我觉得O(m*2^n)里面的m还可以排列一下，应该为O(m!*2^n)

lyg_wangyushi

每一种控制行不变，只改变列的情况，只要检查每一行是否反面多于正面就可以了。
也就是对应确定的先改变列的状况，只要检查所有的行，所以不用对行进行排列。

lijekk

嗯，先改变列反面较多，再改变行，是不错
但是改变行之后，列又发生变化，然后改变列，再改变行,一直循环
这样复杂度为n+m+n+m+............

不过如果反过来首先改变行再改变列的话，得到的结果可能会跟上面的不同，也就是说上面得到的不一定是最优解

还可以先把反面的聚集到几个行或几个列再统一翻转
要完全遍历的话恐怕得 2^m * 2^n才行

mathe

lijekk可以先仔细阅读一下我在12楼的内容，然后再想想是否可以先改变列后改变行。