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实现局部。
第4题代码

后面到期中考试两周基本上是连着的，一者要AC USACO，二者再顺带总结一下DP。

posted on 2012-03-30 23:28 zyn.cpp 阅读(204) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年2月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜