NOIP复赛模拟题(测试数据丢失) [复制链接]

第三题：爱心蜗牛
本题的主要思路是树形DP，难度中等。
细细读题之后，不难看出，题目中虽然明确的强调了上级和下级的关系，但是由于每个人在一个
时间内即可以通知上级也可以通知下级，因此上级和下级实际上是没有区别的。所以我们把这棵
树看作一颗无根树。任意选一条鱼作为根节点，构造一个有根树，分析题目的最优性质。
用f[k]表示通知完以k为根的子树所需要的最短时间。以根节点root为例，我们来考虑f[root]的求
法。显然，对于边界值f[leaf]，即叶子节点而言，f[leaf]=1，但是对于非叶节点，问题就稍微
复杂了一些。由于开始的时候我们只通知了root，那么root的所有直接儿子只能从root这里得
知消息，并且我们假设root所有儿子的f值已经求出。那么root到底先通知那个儿子比较好呢？
假设root的儿子为s1,s2,s3,…sn ，且f[s1]>f[s2]>f[s3]…>f[sn]，则我们让root在每个单
位时间内依次通知s1,s2,s3..sn,得到的结果是最优的。也就是f[root]=max{f[sk]+k}.也就是
说哪个儿子的f值最大我们先通知谁。这个是看起来很显然的结论。但是我们需要证明它。简略证
明如下：
假设root的儿子为s1,s2,s3,…sn,且f[s1]>f[s2]>f[s3]…>f[sn].则我们要证明：
f[root]=max{f[sk]+k}是最优的。
我们把通知儿子的次序中任意交换两个。即原来有 k<j,且 f[sk]>f[sj].，通知这两颗子树的最短
时间是 min{f[sk]+k,f[sj]+j}；当交换顺序以后，则通知这两个子树的最短时间
是Min{f[sk]+j,s[sj]+k},因为 f[sk]>f[sj] 且 j>k, 则我们交换顺序后的到的最小值显然不会比
原来的最优值更优。因此算法得到证明。
由此得到了我们的主算法：枚举每个节点当作树根，建立无根树。每次进行一次树形动态规划，
方程为f[k]=max{f[sj]+j} 其中sj是k的儿子。

第四题：巧置挡板
本题是本次模拟赛中难度最大的题目，从评测情况来看也印证了我们在赛前关于这题得分率的估计。
首先，有不少同学对于题目的理解出现了一定的偏差，在题目中我们强调了“隔离室有且只有一条鱼”，考虑下面这个例子：
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[x1,x2,y1,y2]的棋盘分割，如果我们认为这个值是满足最优子结构性质的话，那么状态转移也就是trivial的，即O(n)的状态转移：
最优的值等于两个子矩形最优值的和。
这样的DP其时间复杂度是O(n^5)的，而且肯定可以对应一种合法的方案，但是这个解是否一定是最优解呢？测试发现，样例和一些数据都可以过掉，实际上，这样的DP已经可以过掉我们的测试数据中的8个测试点，但是这个DP的基础是什么呢？
实际上，这样的DP有一个假设是，最优解都是一刀切“到底”的，这样才可以用枚举某个[x1,x2,y1,y2]的矩形中的切割边的方法来实现O(n)的状态转移，但是实际上这个结论是不正确的，请看下例：
0 0 0 0 0|0 0
0 0 0 0 0|0 0
0 0 0 0 0|0 0
0 0 0 0 1|1 0
---+-----+
0 0|1 0 0|0 0
+-----+---
0 1|1 0 0 0 0
0 0|0 0 0 0 0
0 0|0 0 0 0 0
这组数据用普通的DP的结果是20，可是最优结果是19，原因就在于最优切割方案中没有任何一刀是直接“切到底”的，这样就说明了上述的O(n^5)DP是错误的，但是这个DP的结果并不是没有用处。
我们的标程采用的算法是搜索，上文说过DP的结果尽管不是最优解，但是是一个相当接近最优解的上界，因此在搜索的时候，首先用DP给出一个上界，然后将这个值作为剪枝的条件可以大大加快出解的速度。
搜索的大体思路是这样的，对每一个1，枚举仅仅包含这一个1的矩形，然后不停的搜下去，这个思路是比较简单的，也是不难实现的，如果没有以刚才的DP出的值作为上界的话，搜索的效率是很低的。
对本题数据的说明：由于本题没有同学用标程的算法提交，因此我们将数据的难度减弱了，有8个点的数据都是可以通过一刀切的方法搞出来的，这也是为了提高本题的得分率。（要不然对于那些O(n^5)DP的同学而言比较不公平了撒）

怎样增加威望呀？

非常感谢，希望以后多一些模拟题

非常感谢，希望以后多一些模拟题

thanks vevy much

把整个程序都公布出来啊!

及时雨

太感谢了

谢谢　７楼的方法真不错