回帖：第四题：巧置挡板
本题是本次模拟赛中难度最大的题目，从评测情况来看也印证了我们在赛前关于这题得分率的估计。
首先，有不少同学对于题目的理解出现了一定的偏差，在题目中我们强调了“隔离室有且只有一条鱼”，考虑下面这个例子：
1 0 0
1 0 0
1 0 0
有些同学认为这样的最优方案是5个挡板，实际上是6个挡板。
5个挡板的分割是这样的：
1|0 0
-
1|0 0
-
1|0 0
但是右边的那个隔离室里面没有鱼，因此是不满足条件的，最优解只能是这样的6个挡板：
1 0 0
- - -
1 0 0
- - -
1 0 0
这是关于题目理解的题目。
其次，有不少同学在这题上用了O(n^5)的DP，方法我简述如下：
NOI 99有一道题目叫做棋盘分割，（限于篇幅本人在此不再赘述此题的做法，大家可以参见刘汝佳的书P.116关于此题的分析）有些同学选择了和这题DP方法类似的状态表示和转移进行DP，但是实际上这样的DP是错误的。
棋盘分割的DP，其状态表示通常是四维或者是五维的，比如f的棋盘分割，如果我们认为这个值是满足最优子结构性质的话，那么状态转移也就是trivial的，即O(n)的状态转移：
最优的值等于两个子矩形最优值的和。
这样的DP其时间复杂度是O(n^5)的，而且肯定可以对应一种合法的方案，但是这个解是否一定是最优解呢？测试发现，样例和一些数据都可以过掉，实际上，这样的DP已经可以过掉我们的测试数据中的8个测试点，但是这个DP的基础是什么呢？
实际上，这样的DP有一个假设是，最优解都是一刀切“到底”的，这样才可以用枚举某个的矩形中的切割边的方法来实现O(n)的状态转移，但是实际上这个结论是不正确的，请看下例：
0 0 0 0 0|0 0
0 0 0 0 0|0 0<