AC. 梦想

frank_c1

[BZOJ 1210] 邮递员

发布于2016年04月13日 | 暂无评论 | 2,045阅读 | 状态压缩,连通性

题目描述

Smith在P市的邮政局工作,他每天的工作是从邮局出发,到自己所管辖的所有邮筒取信件,然后带回邮局。他所管辖的邮筒非常巧地排成了一个m \times n的点阵(点阵中的间距都是相等的)。左上角的邮筒恰好在邮局的门口。 Smith是一个非常标新立异的人,他希望每天都能走不同的路线,但是同时,他又不希望路线的长度增加,他想知道他有多少条不同的路线可走。你的程序需要根据给定的输入,给出符合题意的输出。输入包括点阵的mn的值,你需要根据给出的输入,计算出Smith可选的不同路线的总条数。

输入格式

只有一行。包括两个整数m,n(1 \le m \le 10,1 \le n \le 20),表示了Smith管辖内的邮筒排成的点阵。

输出格式

只有一行,只有一个整数,表示Smith可选的不同路线的条数。

题目解析

这是插头DP的经典入门题了吧。题目所求即为网格图上经过所有点的哈密顿回路数量\times 2

我们采用括号表示法来表示状态。'('表示左插头,')'表示右插头,'\#'表示无插头。

状态的转移比较复杂,需要仔细分析。设当前决策格的左侧和上侧的插头为(a,b),则有

1.('\#','\#') : 左侧和上侧都没有插头连入。因为每个格子必有两个插头,故向下、向右有插头,也就是开始一个新的连通分量,转移到('(',')')

2.('(','\#') : 左侧有插头连入,上侧没有。我们只需延续原来的连通分量,可以继续向右延伸转移到('\#','('),也可以转向下延伸转移到('(','\#'),注意边界情况。

3.(')','\#') : 类似2处理方式。

4.('\#','(') : 上侧有插头连入,左侧没有。处理方式同2,3。

5.('\#',')') : 类似4处理方式。

6.('(',')') : 左侧有左括号插头连入,上侧有有右括号插头连入。那么把它们连起来就圆满啦,刚好构成一条回路。但是注意这种情况只可发生在最后的格子(右下角),此时需要更新答案。

7.('(','(') : 左侧和上侧都有左括号插头连入。这时我们在合并两个联通分量,将它们连起来后,原来与上侧插头相匹配的右括号插头应该变成左括号插头,于是我们找到与上侧插头相匹配的右括号插头修改一下状态即可。

8.(')',')') : 左侧和上侧都有右括号插头连入。处理方式类似7,找到与左侧插头相匹配的左括号插头修改一下状态。

9.(')','(') : 左侧有右括号插头连入,上侧有左括号插头连入。就是将两连通分量连接起来,转移到('\#','\#')

时间复杂度O(nm 3 ^ m)。膜一膜CDQ的著名论文《基于连通性状态压缩的动态规划问题》。