c++&oi

随便说说状态压缩

状态压缩是信息学竞赛中一个很常见的方法,最最常见的是二进制压位。
做过USACO的同学会知道有很多搜索和DP都可以用状态压缩优化。

一般来讲,如果状态的够成非常多,但每个构成相对简单,就可以状态压缩,比如巨大的0/1矩阵等。
当然如果状态压缩,提取每个数据起来就会耗费更多的时间,所以一般运用在状态复制量较大,比较量较小的情况下。

举例:

多关键字排序可以用状态压缩,如A,B,C三个关键字,均小于100,可以压缩成A*10000+B*100+C,直接比较即可,非常方便。

N皇后的状态压缩,配合位运算,神速。

相邻两行之间的匹配关系,压成二进制,做DP。

其实只要想节约空间都可以用状态压缩。
压缩通式:0<a<A 0<b<B 0<c<C   (关键程度a>=b>=c)  <==> T=a*B*C+b*C+c ,A*B*C<maxstruct
为了方便一般使A=B=C,转换成A进制数即可

(*)状态压缩的效率:
常见的把5个小于100的数压成一个longint的数,如果是5个小于50的数呢?
1.空间利用率:显然按十进制压缩的空间效率太低,可以考虑按50为一个单元压缩,
2.时间效率:提取时大量的取模和除法运算使效率太低,可以考虑换成64进制的数,进行压缩。
这里的空间又有了一定程度上的浪费,也体现了时间与空间的辩证关系。

posted on 2011-12-04 13:07 zyn.cpp 阅读(1501) 评论(0)  编辑 收藏 引用


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


<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜