蓝桥杯 格子刷油漆

问题描述

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

　　

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

输入格式

　　输入数据为一个正整数（不大于1000）

输出格式

　　输出数据为一个正整数。

样例输入

2

样例输出

24

样例输入

3

样例输出

96

这道题，根据数据量便可得知，使用的算法应该是动态规划，难点在于需要从第一个刷漆的格子的位置，将整体分成左右两半， 先刷一半，再刷另一半

dp[i][0]表示从第i个格子出发，刷满前i个格子后，最后回到第i个格子的方法数， dp[i][1]表示从第i个格子出发，刷满前i个格子后没有回到第i个格子的方法数。

下面是我的ac代码：

 1 #include<iostream>
 2 using namespace std;
 3 #define MAX 1020
 4 long long dp[MAX][2],ans;
 5 int main(){
 6     int m;
 7     cin>>m;
 8     dp[1][0]=2;dp[1][1]=0;
 9     dp[2][0]=4;dp[2][1]=8;
10     for(int i=3;i<MAX;i++){
11         dp[i][0]=(dp[i-1][0]*2)%1000000007;
12         dp[i][1]=2*(dp[i-1][0]+dp[i-1][1])%1000000007+4*(dp[i-2][0]+dp[i-2][1])%1000000007;
13     }
14     //从两端开始回到两端 以及从两端开始不回到两端 
15     ans=2*(dp[m][0]+dp[m][1])%1000000007;
16     //此处累加遍历第一个被刷的格子的列 
17     for(int i=2;i<m;i++){
18         //从中间第i位置开始先右后左 
19         ans+=(dp[i][0]*(dp[m-i][0]+dp[m-i][1]))%1000000007;
20         //从中间第i位置开始先左后右 
21         ans+=(dp[m-i+1][0]*(dp[i-1][1]+dp[i-1][0]))%1000000007;
22         ans%=1000000007;
23     }
24     cout<<ans<<endl;
25     return 0;
26 }

测评结果：