0%

Topcoder专题3

A DiagonalColumn

题意

一个$n\times m$的网格,一开始所有格子都是白色的,你可以进行若干次操作。每次操作你选择一列或者一条从左上到右下的对角线,然后将这条线上的所有格子都染黑。(对角线一共有$n+m-1$条)。问最后有多少种可能的染色方案。

题解

想了一早上。

我们先考虑右上角的这个格子。

image-20210129201150129

如果这个格子所在的对角线选了,那么这一列选不选对这个格子最终的颜色并没有影响。此时我们可以直接将这个格子删去,对网格剩下的部分求出方案数。

否则,这个格子一定是白色(否则我们可以当作选了对角线处理),此时这个格子所在的列一定没有被选,考虑这些对角线

image-20210129201721340

由于最后一列没有选,因此这些对角线是否选择会在最后一列的格子中反应出来,即如果这些对角线选择的方案不同,最后的染色方案也一定不同。

考虑更一般的问题:对于下面这个多边形:

image-20210129202306251

考虑最靠右上的这条对角线:如果这条对角线选,那么线上的格子可以删去,接下来是子问题。

否则,第$i$列及之后的列是否选择都会在这条对角线上反应出来,并且这些列不能全部选。此时一定存在最靠前的一列没有被选,我们记这一列为$j$。

注意,此时$[i,j)$这些列全部被选,$(j,m]$这些列可选可不选。

考虑在$j$之后的那些对角线,这些对角线是否选择也能在第$j$列反应出来。如果这些对角线全部选,那么矩形将只留下由第$j-1$条对角线以及第$i-1$列包围的部分,这是子问题。

否则,又有一些列的状态会在某条对角线上反应出来,继续考虑会导致这种“反应”一直嵌套下去,这启发我们重新设计状态。

考虑这样一个状态:记$dp[i][j][k]$表示考虑由第$k$条对角线与第$i$列围成的多边形,其中第$j$列到第$i$列选择方案不同则视为最终方案不同的染色方案数。

此时$dp[m][m+1][n+m-1]$就是答案。

接下来考虑如何转移。

image-20210129203826809

当$j=i+1$时:

如果$k$这条对角线选,转移到$dp[i][j][k-1]$。

否则,$k$对下来的列到第$i$列不能同时选,容斥掉这种情况,接着第$k-n+1$列到第$i$列是否选都会在这条对角线上反应出来,转移到$dp[i][k-n+1][k-1]$。

当$j\leq i$时:

先判掉第$j$列到第$i$列全选的情况,此时这些列可以全部删掉。

否则,一定存在某一列没有被选,枚举这一列,不妨设为$l$。

$l$以上的对角线是否选择都会在第$l$列反应出来,判掉这些对角线全选的情况,此时这些对角线和$j$列之后都可以删掉。

接着枚举最靠下的没有被选的这条对角线,假设为$t$,此时第$t-n+1$列到第$j-1$列是否被选会在这条对角线上反应出来,这恰好可以用我们的$dp$状态表示,转移到$dp[j-1][t-n+1][l-1]$。

代码