85/100
题意:
现有一个$n*m(1\le n,m\le100000)$大小的网格,你现在要将所有格子涂成白色或者黑色,并且相同颜色连续(上下左右相连)的格子不能超过两个,求方案数$\%10^9+7$。
题解:
这种题可以直接打表过。
正解是推出dp,首先我们要明确一点,就是上一行和下一行的状态完全相反,在满足这个条件的情况下,我们可以将行列分开计算。
当上一行出现连续相同的颜色时,那下一行的颜色就与上一行完全相反,当未出现这种情况时,那下一行也必须满足该条件,那么整体方案就由第一行确立,列同理。
那再想想计算的方案:
设$dp_{i,j}$为当前格子为$i$,颜色为$j$(0为白,1为黑)时的方案数,那么:
$dp_{i,0}=dp_{i-1,0}+dp_{i-2,1}$
$dp_{i,1}=dp_{i-1,1}+dp_{i-2,0}$。
合并可得$dp_i=dp_{i-1}+dp_{i-2}$。
而行列都会出现同一种情况即黑白相间,且黑白相间本身有两种,那么答案即:
$dp_n+dp_m-2$。
- 本文作者: baddog
- 本文链接: https://katoli.github.io/2021/06/23/CF-1239A/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!