IOI2008 中国国家集训队论文 长沙市雅礼中学 陈丹琦
第 6 页
【确立状态】 先提出一个非常重要的概念——“插头”.对于一个 4 连通
的问题来说,它通常有上下左右 4 个插头,一个方向的插头存在表示这个格子在
这个方向可以与外面相连.本题要求回路的个数,观察可以发现所有的非障碍格
子一定是从一个格子进来,另一个格子出去,即 4 个插头恰好有 2 个插头存在,
共 6 种情况.
逐行递推
不妨按照从上到下的顺序依次考虑每
一行.分析第 i 行的哪些信息对第 i + 1 行有影响:
我们需要记录第 i 行的每个格子是否有下插头,这决
定了第 i+1 行的每个格子是否有上插头.仅仅记录插
头是否存在是不够的,可能导致出现多个回路 (如右
图),而本题要求一个回路,也就隐含着最后所有的非障碍格子通过插头连接成
了一个连通块,因此还需要记录第 i 行的 n 个格子的连通情况.
插头:0011 插头:1111 插头:1001
连通性:(3,4) 连通性:(1,2) (3,4) 连通性:(1,2,3,4)
我们称图中的蓝线为轮廓线,任何时候只有轮廓线上方与其直接相连的格子
和插头才会对轮廓线以下的格子产生直接的影响.通过上面的分析,可以写出动
态规划的状态:
表示前 i 行,第 i 行的 n 个格子是否具有下插头的一
个 n 位的二进制数为
的方案总数.
如何表示 n 个格子的连通性呢? 通常给每一个格子标记一个正数,属于同一
个的连通块的格子标记相同的数.比如{1,1,2,2}和{2,2,1,1}都表示第 1,2
个格子属于一个连通块,第 3,4 个格子属于一个连通块.为了避免出现同一个
连通信息有不同的表示,一般会使用最小表示法.
一种最小表示法为:所有的障碍格子标记为 0,第一个非障碍格子以及与它
连通的所有格子标记为 1,然后再找第一个未标记的非障碍格子以及与它连通的
格子标记为 2,……,重复这个过程,直到所有的格子都标记完毕.比如连通信
息((1,2,5),(3,6),(4))表示为{1,1,2,3,1,2}.还有一种最小表示法,即一
个连通块内所有的格子都标记成该连通块最左边格子的列编号,比如上面这个例
括号内的数表示的是格子的列编号, 一个括号内的格子属于一个连通块