9.9模拟总结

模拟赛笔G

总体上：

这一次考试真的是dp专场，我全部打的暴力部分分，难受的一批！
主要是我个人的dp能力太薄弱了......

个体上：

第一题：

在考场上我的状态设计的很正确，但是没有想出正解，也没有想到过单调队列优化这些事。

总结：

dp的优化除了直接时间上优化，还可以通过减少状态数来优化。
就比如这道题，发现最优答案都是满足一定规律的，总共满足此规律的状态数量在n*n左右。

第二题：

改编自：Exclusive Access 2
状态压缩dp的大致方向是想的没有问题的。
关键是不清楚dliworth定理。
所以dp想了半天的转移也没有想出来，最后暴力......

正解：
一个结论：有向无环图的最长链点数等于最小的点集划分数使得每个点集中不存在两点有路径。

证明：
由于最长链上的两点必然不能属于同一个点集，所以点集划分数大于等于最长链长度。

我们可以每次选出度为零的所有点划分在同一个点集中，若这些点之间有路径，则和他们出度为0
矛盾，所以这样划分一定合法。同时，这样划分的集合数恰为原图的最长链长度。

第三题：

只想到了n=1的怎么做，因为互相影响的时候就不知道怎么dp了.....

第四题：

同上，时间不够就想打第一问，没有仔细思考过怎么dp。