培训作业-第六周（DP++） - c++&oi

培训作业-第六周（DP++<2>）

由于明天就要上下个星期一的课了，这个星期就算就此结束了。
总结一下，这个星期主要是完成一套DP练习题。4题150分钟。
现场考的时候大悲剧245/400，据说省队水平基本上是300+。
第一题钓鱼各种边界挂掉，WA了三个点。
第二题旅游路线唯一AC的一道题，树形DP。
第三题 Ticket Office 觉得是O（n）DP但不会写，于是贪心55/100
第四题广场铺砖状态压缩DP，竟然来不及思考了，果断些了无解和n=2的情况，20/100.

第三题是ceoi2005的题，
貌似比原题简单，我后来写了一个显然会漏解的DP 90/100
按照网上所说的贪心方法写80/100，
仔细想想应该是贪心+DP，但怎么调不是80就是90，于是放弃了
实在不值得。。。

第四题貌似当场有1h也想不出来。
一开始想的是用1表示横放，2表示竖放，0表示被占据
后来发现虽然是O(3^n)的状态数，但三进制不能操作，转移必挂。
让后又想出了记录两行的O(2^(2*n))的状态数，
经过dfs试验只有10000多种状态，虽然远小于2^22但还是会挂。
于是终于才知道只要用一行的0/1储存就行了，不过转移时要顺带算出下一行的。
于是O（h*(2^(w))^2）算法形成了。
实现时用主动更新的方法。用DFS实现局部。