[蓝桥杯][2013年第四届真题]格子刷油漆

题目

题目链接

题解

思维吧，动态规划。 根本不会。

定义两个数组： a[i]表示在一个2×i的网格中最左边一列和最右边一列的四个格子，从以其中任意一个格子为起点进行涂漆的全部方案数（这四个位置作为起点方案数相同）； b[i]表示在一个2×i的网格中最左边一列和最右边一列的四个格子，从以其中任意一个格子为起点进行涂漆，且终点为起点上面或下面的格子（我们称之为相邻的格子），这样的方案数。

我们可以发现涂漆的特点： 假如我们涂到格子(1, c)，思考如何涂下一个格子。如果左侧和右侧都存在格子没有被涂上漆，那么我们绝对不能在涂完格子(1, c)后涂格子(2, c)，因为此时涂格子(2, c)，相当于用第c列将左右两部分隔开了，涂完这一列后下一步无论是向左还是向右涂，之后都无法到达另一边，而由于两边都存在空格子，所以无法将全部格子上色。

b[]数组的赋值比较简单： 这是一个2×i的网格，假设起点是左上角(1, 1)（左下、右上、右下类似），终点为左下角(2, 1)。

从起点开始，先涂起点，接着只能选择涂(1, 2)或者(2, 2)，分别对应蓝色格子和紫色格子。 假设涂的是蓝色格子，则下一步只能涂(1, 3)或者(2, 3)，这是因为由上面的“涂漆的特点”可知，左侧和右侧都存在空格子，下一步不能涂相邻格子，因此我们在(1, 3)或者(2, 3)选择一个格子涂漆，之后也是类似，从(1, 4)和(2, 4)中选择，从(1, 5)和(2, 5)中选择，直到第i列，涂完第i列两个格子中的一个后，我们必须将其相邻的格子也涂上，之后只需要沿着未涂的格子顺着回到终点即可，这段路程中无需选择，因为每列就一个空格子。

我们可以求出b[i]了吧。如果还不是很理解如何确定b[i]可以看一下下面的图，一棵二叉树： 有2^(i-1)个叶子结点吧，就是方案数，因此b[i] = 2^(i-1)或者递推表示为b[i] = 2*b[i-1]，其中b[1] = 1。

a[]数组的赋值就比较难搞些了。 回顾一下a[]的定义，表示在2×i的网格中以四个角中的其中一个为起点的方案数。 相较于b[]，a[]并不限制终点的位置。

我们分情况讨论一下：

涂完起点之后，存在三种选择，涂相邻格子（粉），涂右侧格子（蓝），涂右下格子（紫）。 我们想得到以左上角为涂漆起点的方案总数，即a[i]，又即三种情况的方案总数之和。

选择涂粉色格子：涂完粉色格子后，相当于第一列被消除了，之后的如何涂漆与第一列几乎没关系了。唯一的关系就是涂完粉色格子之后可以选择涂蓝色格子或者涂紫色格子。好了，我们先仔细看看，第一列被消除了，那么网格变成2×(i-1)了，相当于问题的规模从i变到了i-1，而且涂完粉色之后存在两种选择，蓝或紫，而无论以蓝色还是紫色为起点，在2×(i-1)的网格中进行涂漆，都具有相同的总方案数，即同为a[i-1]。当涂完起点处格子后，选择对相邻格子进行涂漆，方案总数为2*a[i-1]。

选择涂蓝色格子：涂完蓝色格子后，我们又可以进行选择了，是“将粉色格子涂上漆，即消除第一列之后处理剩下的格子”还是“不消除第一列，先处理其他格子，最后再涂粉色格子”。反正肯定不能涂紫色格子吧。其实就是要么往左涂，要么往右涂。

选法一：（上图）如果我们在涂完蓝色格子后选择向左涂，即涂粉色格子，那么第一列被消除，接下来的涂色也是固定的，即涂紫色格子。也就是说，当我们选择路径为起点 -> 蓝色 -> 粉色后，粉色 -> 紫色的路径也就固定了。 这样我们将第二列也消除了，现在只剩第三列及其右侧的格子了。涂完紫色格子，问题规模变成了i-2，接下来我们又可以选择灰色或者黄色，而且进行这两种选择后的方案数也是一致的，为a[i-2]。 因此我们在涂完蓝色格子后选择涂粉色格子（接下来只能涂紫色格子），这样得到的方案数为2*a[i-2]。

选法二：（上图）如果我们在涂完蓝色格子后选择向右涂，即要么选择涂灰色格子，要么选择涂黄色格子，而且我们可以推断出倒数第一个被涂的格子一定是粉色的，倒数第二个一定是紫色的。细心（天才）的同学会发现，忽略第一列，起点就是蓝色格子，终点就是与蓝色格子相邻的紫色格子，这不和b[]数组的赋值原理一样吗，即每次选择一列中的一个涂色，到达第i列返回时只需涂上空格子即可。因此这种情况下，对应的方案数正是b[i-1]。

选择涂粉色格子：涂完紫色格子后，类似于“涂完蓝色格子”后的选择，我们还可以进行两种选择：“涂完紫色后涂粉色，再之后只能涂蓝色格子”和“涂完紫色后先处理其右侧的格子，都涂完了之后再涂蓝色格子和粉色格子”。还是可以将这两种情况理解为左涂和右涂。

方法一：（上图）如果我们涂完紫色后选择涂粉色，接着只能涂蓝色，问题同“选择涂蓝色格子”中的“方法一”一样，都是转化成了规模为i-2的问题，即方案数为2*a[i-2]。

方法二：（上图）如果我们涂完紫色后选择涂其右侧的格子，那么倒数第一个被涂的格子一定是粉色格子，倒数第二个被涂的一定是蓝色格子，不妨忽略第一列，问题就转化成了从紫色格子涂起，到蓝色格子终止的方案数，这与“选择涂蓝色格子”中的“方法二”一样，即方案数为b[i-1]。

（你是不是都快忘了咱们在干什么了） 综上，我们实现了对数组a[]的赋值，a[i]表示在2×i的网格中以四个角中的其中一个为起点的方案数。把上面的全部方案数一加就是a[i]了，即a[i] = 2*a[i-1] + 4*a[i-2] + 2*b[i-1]。

出现了新问题，数组a[]保存的只是四个角出发的方案数啊，那假如从第4列的两个格子中的其中一个出发呢，要是第5列呢？第8列？显然这些情况的第一步的选择和四个角第一步的选择大不相同啊。

但是我们可以转化为四个角。 对于中间列为起点的情况我们可以分为两种情况，一种是先向左涂再向右涂，另一种为先向右涂再向左涂，其实两种情况类似。

首先我们必须明确一点，还是根据“涂漆的特点”，必须要先涂完一侧的再涂起点相邻的格子，再涂另一侧的格子。 假设网格为2×n的规格，起点所在列为第i列，1 < i < n。

先左后右： （上图）从起点开始可以选择起点左侧一列的上面格子或下面格子，自此向左涂，涂到第一列后涂完剩下的空格子，回到起点下面的相邻格子，这个过程和对b[]数组进行赋值的过程又是一样的，即涂完左侧全部格子的方案数为b[i]。 涂完左侧后，要从起点的相邻格子开始向右涂色，可以选择起点的右侧的格子，也可以选择起点的右下侧格子，对于起点右侧这一列向右涂色来说，其实就是对右侧的n-i列进行上色，将问题的规模化为n-i，即a[n-i]，因为有两种方案数相同的选择，因此涂完右侧全部格子的方案数为2*a[n-i]。 两部分乘起来为“先左后右”的方案总数2*a[n-i]*b[i]。

先右后左： （上图）类似的，可以得到从涂完右侧格子的方案数为b[n-i+1]； 涂完左侧格子的方案数为2*a[i-1]； 两部分乘起来为“先右后左”的方案总数2*a[i-1]*b[n-i+1]。

最后一步了！

我们只需要遍历每一列，将以每一列的两个格子为起点的方案数加起来就是最终答案了。

注意几点：

1. 初始化时，b[1] = 1，后续可以通过乘2得到；a[1] = 1, a[2] = 6，之所以要将a[2]也进行初始化，是因为上面咱们求得的递推公式中a[i]的计算要用到a[i-2]的值；
2. 我们上面求的 “先左后右”和“先右后左”各自的方案总数都只是针对起点所在列中的一个格子的情况数，而一列俩格子，因此要在遍历累加的时候*2；
3. 不要忘记单独加上四个角的为起点的方案数，4*a[n]；
4. 其实就是将这个2×n的网格的每个格子作为起点的方案数相加。

代码

#include
using namespace std;
typedef long long ll;
const int N = 1010;
const ll MOD = 1000000007;

int n;
ll ans;
ll a[N], b[N];

int main()
{
	cin>>n;
	
	b[1] = 1;
	for(int i = 2;i