蓝桥杯-格子刷油漆-动态规划-java

问题描述 　　X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。 　　你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！） 　　比如：a d b c e f 就是合格的刷漆顺序。 　　c e f d a b 是另一种合适的方案。 　　当已知 N 时，求总的方案数。当N较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。 输入格式 　　输入数据为一个正整数（不大于1000） 输出格式 　　输出数据为一个正整数。 样例输入 2 样例输出 24 样例输入 3 样例输出 96 样例输入 22 样例输出 359635897 解题思路：像这种题大多数是动态规划          既然用动态规划来做那么我们就要分析状态          题是从任意一个格子刷刷完整面墙有多少种方法          情况太多了所以我们要简化状态          我设格子这么排列总共两层          1 2 3 .......n          1 2 3 .......n          我从第一层开始刷：            我第一次刷第一层的1号格            然后把墙刷完有x种方法            我第一次刷第一层的2号格            然后把墙刷完有y种方法            所以求的方案数=（x+y+.....）*2            对称吗所以乘2就可以了          之后的操作就是将x，y....求出来：            咱们先模拟一下               1  2  3  4  6  7  n=7              -1 -2 -3 -4 -6 -7            我先假设我从3号格开始刷             根据题意有两种方案刷墙             1.把3号格的左面刷完然后经过               -3号格再把右面刷完             2.把3号格的右面刷完然后经过               -3号格再把左面刷完             咱们先看第一种方案：               我不管左面怎么刷他最后一定要回到-3号格               设在回到-3号格的方案数是a               然后我们把右面刷完               右面只要刷完就可以了               不限制最后一步你在哪里               设右边随便刷的方案=数是b               那么第一种总的方案数=a*b             第二种方案::                还是和上面同理               我不管右面怎么刷他最后一定要回到-3号格               设在回到-3号格的方案数是c               然后我们把左面刷完               左面只要刷完就可以了               不限制最后一步你在哪里               设左边随便刷的方案=数是d               那么第一种总的方案数=c*d       综上所述得出 x=a*b+c*d               那么问题来了abcd怎么求       继续向着本质前进          以上我们得出两种状态                1.随便刷                2.最后一步要回到选定格子的下面          状态1，2分析：                随便刷表示的是最后一步落在任意位置                所以随便刷的方案数包含状态2的方案数                随便刷= 最后一步要回到选定格子的下面的方案数+最后一步不落在选定格子的下面的方案数           这样又出现了状态3：                3.最后一步不落在选定格子的下面                咱们先求状态2.3                接着上面的模拟                我们选定的是3号格                  1  2  3                 -1 -2 -3                 总共有六种类型                 2 ——— -2 ——— 1 ———— -1     1种走法   没到-2回不到-3因为2已经被刷过了不能踩                 2 ——— -2 ——— -1 ——— 1      1种走法   同上                 2 ——— 1 ——— -2 ——— -1      1种走法   同上                 2 ——— 1 ——— -1 ——— -2      1种走法   回到-2下一步就可以回到-3                 2 ——— -1 ——— 1 ———— -2     1种走法   同上                 2 ——— -1 ——— -2 ———— 1     1种走法   同第一个                 -2打头走都一样因为对称吗！                 2*2随便排=6                 上面模拟的是2*2                 再模拟2*3总会找到规律（状态方程）                 1  2  3  4                -1 -2 -3 -4                 还是六种类型                 3 —— -3 —— 2 ......         这种类型的种数实际上就是2*2的随便排    6种                 3 —— -3 —— -2 ......        同上                                6种                 3 —— 2 .......—— -3         实际上就是2*2最后一步要回到-2的方案数   1+1=2种                 3 —— -2 ......—— -3         同上                                  2种                 3 —— 2 —— -3 —— -2 ....     2*1的随便排 1+1=2种                                     3 —— -2 —— -3 —— 2 ....     同上            2种                 -3打头也一样对称                 2*3 的随便排 6+6+2+2+2+2=20                 2*4可以自己模拟一下                 以下是代码： import java.util.Scanner; public class Main {      public static void main (String [] args){     long [] [] arr = new long [1001][7];     arr[1] [6] = 1;     arr[2] [0] = 1;arr[2] [1] = 1;arr[2] [2] = 1;     arr[2] [3] = 1;arr[2] [4] = 1;arr[2] [5] = 1;arr[2] [6] = 6;     for (int i = 3 ; i < 1001; i++) { arr[i][0] = (arr[i-1][6])00000007; arr[i][1] = (arr[i-1][6])00000007; arr[i][2] = (arr[i-1][2]*2)00000007; arr[i][3] = (arr[i-1][3]*2)00000007; arr[i][4] = (arr[i-2][6]*2)00000007; arr[i][5] = (arr[i-2][6]*2)00000007; arr[i][6] = (arr[i][0]+arr[i][1]+arr[i][2]+arr[i][3]+arr[i][4]+arr[i][5])00000007; }     Scanner scanner = new Scanner(System.in);     while (scanner.hasNext()) { int n = scanner.nextInt(); long sum = arr[n][6]*2*2; for (int i = 2; i <= n-1; i++) { long a = ((arr[i][2]+arr[i][3])*arr[n-i][6]*2)00000007; long b = (2*arr[i-1][6]*(arr[n-i+1][2]+arr[n-i+1][3]))00000007; sum += ((a+b)*2)00000007; sum %= 1000000007; } System.out.println(sum); }      } }