尿于it通徃状态圧痞的幼态规刻问龜长沙市雅礼中学陈丹琦【摘要】基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题.在状态压缩的基础上，冇类问题的状态中必须要记录若干个元索的连通情况，我们称这样的问题为基于连通性状态压缩的动态规划问题，本文着重对这类问题的解法及优化进行探讨和研究.本文主要从动态规划的几个步骤——划分阶段，确立状态，状态转移以及程序实现來介绍这类问题的一般解法，会特别针对到目前为止信息学竞赛中涌现出來的几类题型的解法作一个探讨.结合例题，本文还会介绍作者在减少状态总数和降低转移开销两个方面对这类问题优化的一些心得.【关键词】状态压缩连通性括号表示法轮廓线插头棋盘模型【目录】【序言】..........................................................................................3【正文】..........................................................................................5壱.问题的一般解法.....................................................................5【例1]Formula1..............................................................................5问题描述........................................................................5算法分析........................................................................5小结...................................................................................12弐.一类简单路径问题................................................................12【例2]Formula2.............................................................................15问题描述......................................................................15算法分析......................................................................16小结...................................................................................17参.一类棋盘染色问题................................................................17【例3]BlackWhite........................................................................18问题描述......................................................................18算法分析......................................................................18小结...................................................................................20卩q.—类基于非棋盘模型的问题...................................................21【例4】生成树计数............................................................21问题描述......................................................................21算法分析......................................................................21小结...................................................................................22伍.一类最优性问题的剪枝技巧....................................................23【例5]RocketMania......................................................................23问题描述......................................................................23算法分析......................................................................24小结...................................................................................26六.总结....................................................................................26【参考文献】..................................................................................27【感谢】........................................................................................27【附录】........................................................................................28【序言】先看...