【XSY2733】Disembrangle DP

题目描述

  有一个\(3\times n\)的网格,一些格子里已经有棋子了,一些格子里还没有。

  每次你可以选择往一个没有棋子的格子里放一个棋子,但要满足这个格子上下两个格子都有棋子或左右两个格子都有棋子。

  你的任务是把这个网格填满。问你有几种填法。

  \(n\leq 2000\)

题解

  先判无解。

  如果四个角没有棋子或在第\(1/3\)行有两个相邻的空格就无解。

  然后DP。

  可以对于每个连通块分开DP,然后把结果合并。

  可以看出一个连通块只可能通过第\(2\)行相邻。

  设\(f_{i,j,k}\)为前面\(i\)行,\((2,i)\)这个格子在前面所有空格中是第\(j\)个放的,\((2,i+1)\)是否需要在\((2,i)\)之前放 的方案数。

  转移:枚举\((2,i+1)\)是在什么时候放的。

  设\(c\)为第\(i+1\)列两边的空格数。

  \(f_{i,j,1}\rightarrow f_{i+1,l,0}(l\leq j)\),上下都要先放:\(A(l-1,c)\)

  \(f_{i,j,0}\rightarrow f_{i+1,l,1}(l>j)\),上下有一个后放:\(c(l-1)A(cnt-l,c-1)\),两个都后放:\(A(cnt-l,2)\)

  $f_{i,j,0}\rightarrow f_{i+1,l,0} \(,上下都要先放:\)A(l-1,c)$

  其中\(A(n,m)\)为排列数。

  可以用前缀和优化DP。

  还要考虑\((2,i)\)不是空格但\((1,i),(3,i)\)是空格的情况。

  时间复杂度:\(O(n^2)\)

代码

$f_{i,j,1}\rightarrow f_{i+1,l,0}(l\leq j)$,上下要先放:$A(l-1,c)$

$f_{i,j,0}\rightarrow f_{i+1,l,1}(l>j)$,上下至少有一个没放:$c(l-1)A(cnt-l,c-1)$

$f_{i,j,0}\rightarrow f_{i+1,l,0}$,上下先放:$A(l-1,c)$

上一篇:linux 下部署 redis


下一篇:ContentProvider工作原理