基于连通性状态压缩的动态规划问题(同名).doc

IOI2008中国国家集训队论文 长沙市雅礼中学 陈丹琦PAGE 　　　第 PAGE 6 页基于连通性状态压缩的动态规划问题长沙市雅礼中学 陈丹琦【摘要】基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题．在状态压缩的基础上，有一类问题的状态中必须要记录若干个元素的连通情况，我们称这样的问题为基于连通性状态压缩的动态规划问题，本文着重对这类问题的解法及优化进行探讨和研究． 本文主要从动态规划的几个步骤——划分阶段，确立状态，状态转移以及程序实现来介绍这类问题的一般解法，会特别针对到目前为止信息学竞赛中涌现出来的几类题型的解法作一个探讨．结合例题，本文还会介绍作者在减少状态总数和降低转移开销两个方面对这类问题优化的一些心得．【关键词】 状态压缩　连通性　括号表示法 轮廓线　插头　棋盘模型 【目录】 TOC \o 1-5 \h \z \u HYPERLINK \l _Toc187936482 【序言】 PAGEREF _Toc187936482 \h 3 HYPERLINK \l _Toc187936483 【正文】 PAGEREF _Toc187936483 \h 5 HYPERLINK \l _Toc187936484 一. 问题的一般解法 PAGEREF _Toc187936484 \h 5 HYPERLINK \l _Toc187936485 【例1】Formula 1 PAGEREF _Toc187936485 \h 5 HYPERLINK \l _Toc187936486 问题描述 PAGEREF _Toc187936486 \h 5 HYPERLINK \l _Toc187936487 算法分析 PAGEREF _Toc187936487 \h 5 HYPERLINK \l _Toc187936488 小结 PAGEREF _Toc187936488 \h 11 HYPERLINK \l _Toc187936489 二. 一类简单路径问题 PAGEREF _Toc187936489 \h 12 HYPERLINK \l _Toc187936490 【例2】Formula 2 PAGEREF _Toc187936490 \h 15 HYPERLINK \l _Toc187936491 问题描述 PAGEREF _Toc187936491 \h 15 HYPERLINK \l _Toc187936492 算法分析 PAGEREF _Toc187936492 \h 15 HYPERLINK \l _Toc187936493 小结 PAGEREF _Toc187936493 \h 16 HYPERLINK \l _Toc187936494 三. 一类棋盘染色问题 PAGEREF _Toc187936494 \h 17 HYPERLINK \l _Toc187936495 【例3】Black White PAGEREF _Toc187936495 \h 17 HYPERLINK \l _Toc187936496 问题描述 PAGEREF _Toc187936496 \h 17 HYPERLINK \l _Toc187936497 算法分析 PAGEREF _Toc187936497 \h 17 HYPERLINK \l _Toc187936498 小结 PAGEREF _Toc187936498 \h 19 HYPERLINK \l _Toc187936499 四. 一类基于非棋盘模型的问题 PAGEREF _Toc187936499 \h 20 HYPERLINK \l _Toc187936500 【例4】生成树计数 PAGEREF _Toc187936500 \h 20 HYPERLINK \l _Toc187936501 问题描述 PAGEREF _Toc187936501 \h 20 HYPERLINK \l _Toc187936502 算法分析 PAGEREF _Toc187936502 \h 20 HYPERLINK \l _Toc187936503 小结 PAGEREF _Toc187936503 \h 21 HYPERLINK \l _Toc187936504 五. 一类最优性问题的剪枝技巧 PAGEREF _Toc187936504 \h 22 HYPERLINK \l _Toc187936505 【例5】Rocket Mania PAGEREF _