A Crazy Man
ACM
C++博客
首页
新随笔
联系
聚合
管理
随笔-72 评论-126 文章-0 trackbacks-0
状态DP~
http://acm.sgu.ru/problem.php?contest=0&problem=222
这是入门题,数据较大,需要记忆化搜索
http://acm.pku.edu.cn/JudgeOnline/problem?id=1321
上题的提高版,不过数据超小,爆搜都能过
http://acm.sgu.ru/problem.php?contest=0&problem=223
先要预处理出一行中的全部可行状态~
然后DP的时候巧妙的运用位运算进行状态的判断和转移
状态dp中位运算的巧妙运用会大幅度提高程序的效率和帅气程度
http://acm.pku.edu.cn/JudgeOnline/problem?id=1185
非常经典的状态DP,由于攻击范围是两格,所以要保持两个状态,有人用三进制压缩,我觉得太烦了(不能使用飘逸的位运算)
但是[101][2^10][2^10]得状态太大,考虑到2^10中有很多情况是不可到达的
计算下当m=10的时候最多60个合法状态,所以我开了[101][60][60]的数组记忆化DP过了
http://acm.hdu.edu.cn/showproblem.php?pid=2640
teddy大牛的题目,和上题差不多,不过不能重叠放,所以处理比上题烦很多
同样2^8里有很多不可到达的情况,最多之有13种
所以我开[101][13][13]的数组15ms就过了,哈哈
这就好像是
两次状态压缩
最近的DP题目感觉到
把很多不可到达的状态压缩掉
效率会提高超多~也可能让程序从TLE MLE变成AC~
http://acm.pku.edu.cn/JudgeOnline/problem?id=2411
http://acm.hdu.edu.cn/showproblem.php?pid=1400
这道其实很简单,先预处理出当前状态s1到下一状态的可能值s2,hash[1<<m,1<<m]记录,m为较小值
dp[0][(1<<m)-1] = 1
然后经过n*(1<<m)*(1<<m)的循环得出结果dp[n][(1<<m)-1]
http://acm.sgu.ru/problem.php?contest=0&problem=223
两种砖块,除了预处理的时候状态多点,有7种分支,其他的都和上一题一样
(主意一个状态到另一个状态可能会有多种情况,hash的时候要用++而不是true false)
http://acm.hdu.edu.cn/showproblem.php?pid=2280
要求用最少的1铺满所有的空格,其中3是没用的(可以用两个5代替),化简之后使用的方块和上一题一样,一样的预处理后
dp求出最少的1
http://acm.pku.edu.cn/JudgeOnline/problem?id=1038
http://acm.hdu.edu.cn/showproblem.php?pid=2696
http://acm.hdu.edu.cn/showproblem.php?pid=2442
http://acm.hdu.edu.cn/showproblem.php?pid=1755
http://acm.hdu.edu.cn/showproblem.php?pid=1820
http://acm.hdu.edu.cn/showproblem.php?pid=1668
http://acm.hdu.edu.cn/showproblem.php?pid=2518
http://acm.hdu.edu.cn/showproblem.php?pid=1666
http://acm.hdu.edu.cn/showproblem.php?pid=1820
http://acm.hdu.edu.cn/showproblem.php?pid=2315
posted on 2009-07-12 16:40
shǎ崽
阅读(2464)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
QQ:477627586 Email:notnolysuccess@gmail.com
<
2009年8月
>
日
一
二
三
四
五
六
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(4)
给我留言
查看公开留言
查看私人留言
随笔档案
(72)
2009年11月 (1)
2009年9月 (1)
2009年8月 (1)
2009年7月 (3)
2009年6月 (1)
2009年5月 (6)
2009年4月 (11)
2009年3月 (28)
2009年2月 (20)
links
FZU大大AekdyCoin
偶像hhanger
启蒙老师LCY
神牛matrix67
搜索
最新评论
1. re: 半年AC生涯,仅以此文纪念
膜拜巨巨
--zhaop
2. re: 概率题总汇
概率题感觉还没入门T T,求看zjut大牛的文章,感谢楼主。lmh463896910@gmail.com
--Plumrain
3. re: 神奇的舞蹈~~Dancing_Links[未登录]
HDOJ:1530,用dancing links,lz能不能再讲详细点或者求代码?
--柳晴
4. re: 概率题总汇
我也想看浙大牛人文章,可不可以给我也发一份776593191@qq.com。跪谢
--meander
5. re: 树形DP
评论内容较长,点击标题查看
--随心小亚
6. re: 概率题总汇
傻仔大哥,我也想看浙大牛人文章,可不可以给我也发一份
462039091@qq.com
--song
7. re: 概率题总汇
matrix,yms@gmail.com 谢谢啦
--求 zjut一位大牛的文章
8. re: 八数码的A*算法
http://www.acmwiki.com
欢迎光临
--acm百科网
9. re: 半年AC生涯,仅以此文纪念
你不是一般的crazy~~
--Kkxhappy123
10. re: 半年AC生涯,仅以此文纪念
羡慕你的生活,话说我的AC世界就悲剧多了。。
--kisa
阅读排行榜
1. 神奇的舞蹈~~Dancing_Links(11441)
2. 树形DP(6127)
3. hdoj1006~~Tick and Tick(5251)
4. 概率题总汇(3878)
5. PKU——DP专辑(3685)
6. 半年AC生涯,仅以此文纪念(3606)
7. 浙江省历年省赛题+解析(3363)
8. 状态DP~(2464)
9. 神奇的matrix运算(2271)
10. 图论~~要大干一场了--Author McFn(2178)
评论排行榜
1. 半年AC生涯,仅以此文纪念(19)
2. 神奇的舞蹈~~Dancing_Links(13)
3. 概率题总汇(10)
4. hdoj1271解题报告(8)
5. 神奇的matrix运算(8)
6. HDOJ1074~~Doing Homework解题报告(7)
7. hdoj1430~~魔板~~解题报告(5)
8. 一些计算几何基础公式(含5题及相关模板)(4)
9. 树形DP(4)
10. 又学了一招,随机化法,用于比赛时候是在没办法的时候的流氓剪枝(4)