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年5月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜