插头DP.ppt

文档介绍：状态压缩的动态规划问题
棋盘覆盖模型
(1)骨牌覆盖
(2)线段覆盖
状态压缩动态规划
以集合信息为状态
状态总数为指数级
HDU1693
题意:在n*m(1<=N, M<=11 )的矩阵中,有些格子有树,没有树的格子不能到达,找一条或多条回路,吃完所有的树,求有多少种方法。
初步分析
问题特点:
数据规模小
m, n≤12
搜索?
O((mn)!)
状态压缩!
√
棋盘模型
划分阶段:从上到下,从左到右逐格递推
基本概念:插头,轮廓线
基本概念
插头
一个格子某个方向的插头存在
表示这个格子在这个方向与相
邻格子连接一条线.
轮廓线
已决策格子和未决策格子的分界线
轮廓线上方与其相连的
最多有m+1个插头,包括m个下插头和1个右插头.
初步分析
问题特点:
数据规模小
棋盘模型
每个插头是否存在
确立状态
设 f (i, j, S) 表示转移完(i, j) ,轮廓线上从左到右m+1个插头状态为S的方案总数.
如何表示S(m+1位的二进制数)
1
1
1
0
1
无插头标记0,有插头标记1
f (3,2,{1,1,1,0,1})
状态的转移
每次转移相当于轮廓线上当前决策格子的左插头改成下插头,上插头改成右插头的状态.
状态的转移
这题中显然一个格子中要么有两个插头(经过这个格子),要么没有插头(不经过这个格子),因为不可能分叉走,每个格子走一次。