格子刷油漆【动态规划问题】—NYOJ 980

时间:2024-01-22 12:10:21

个人博客页:https://www.scriptboy.cn/198.html

出处:蓝桥杯

题目描述:

X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形(如下图所示),现需要把这些格子刷上保护漆。

你可以从任意一个格子刷起,刷完一格,可以移动到和它相邻的格子(对角相邻也算数),但不能移动到较远的格子(因为油漆未干不能踩!)
比如:a d b c e f 就是合格的刷漆顺序。
c e f d a b 是另一种合适的方案。
当已知 N 时,求总的方案数。当N较大时,结果会迅速增大,请把结果对 1000000007 (十亿零七) 取模。

 

输入:

输入数据为一个正整数(不大于1000)

 

输出:

输出数据为一个正整数。

 

样例输入:

样例输出:

 

思路:

固定起点,由于如果起点在中间(第2~N-1列)可以分为左右两边来讨论,这时起点都是角格子。假如a[i]表示2*i的格子从左上角开始刷刷完所有格子的方案数(其中i表示列数,1<=i<=N),有三种刷法刷完所有格子:

  1. 先向下刷(即先刷左下角),向下刷完之后有两种方法跳到下一列,刷完剩下的i-1列需要2*a[i-1]
  2. 向下一列刷,最后刷左下角,可以看出不能同列刷,只能一直向右刷,且在没有到最后一列之前是不能返回,所以刷完所有格子有2^i个方案;(此种情况比较特殊,后面需要还要用到,所以单独用b[i]存储下来)
  3. 向下一列刷,有两种方案到下一列,然后返回左下角,再刷下一列未刷格子之后,然后有两种方案再到下一列,可见有四种方案到下下列,所以刷完所有格子有4*a[i-2]个方案;

总之,就是左下角格子什么时候刷,造成了不同的情况。如果是起点不在角格子上,不难看出,可以将左右两侧分割成2*i2*(N-i)的矩形,需要其中一个矩形使用第2种刷法刷才能回到另一个矩形中。

参考:https://blog.csdn.net/roosevelty/article/details/50706322

 

AC代码: