問題描述

  X國的一段古城墻的頂端可以看成 2*N個格子組成的矩形（如下圖所示），現(xiàn)需要把這些格子刷上保護漆。

　　你可以從任意一個格子刷起，刷完一格，可以移動到和它相鄰的格子（對角相鄰也算數(shù)），但不能移動到較遠的格子（因為油漆未干不能踩！）　　比如：a d b c e f 就是合格的刷漆順序。c e f d a b 是另一種合適的方案。　　當(dāng)已知 N 時，求總的方案數(shù)。當(dāng)N較大時，結(jié)果會迅速增大，請把結(jié)果對 1000000007 (十億零七) 取模。

輸入格式

　　輸入數(shù)據(jù)為一個正整數(shù)（不大于1000）

輸出格式

　　輸出數(shù)據(jù)為一個正整數(shù)。

樣例輸入

2

樣例輸出

24

樣例輸入

3

樣例輸出

96

樣例輸入

22

樣例輸出

359635897

思路：這道題是一道動態(tài)規(guī)劃的題目，若要刷2*(n+1)個格子，可以考慮這樣六種狀態(tài)

(以下n,n+1分別表示刷第n,n+1列的墻上的格子,a->b表示刷a列墻上的某個格子后再刷b列墻上的格子,~~~可以為空)

A:~~~->n->(n+1)->(n+1)->n->~~~

B:~~~->n->~~~->n->(n+1)->(n+1)

C:~~~->n->(n+1)->n->(n+1)

D:(n+1)->n->(n+1)->n->~~~

E:(n+1)->n->~~~->n->(n+1)

F:(n+1)->(n+1)->n->~~~

則可推得A[n+1]=2*(A[n]+B[n]+F[n]),B[n+1]=2*(B[n]+C[n]+E[n]),C[n+1]=2*B[n]

     D[n+1]=2*F[n],E[n+1]=2*E[n],F[n+1]=2*(D[n]+E[n]+F[n])(推導(dǎo)的時候還是要注意對六種形態(tài)的理解，然后不要遺漏情況) 

注意n=1的特殊情況，直接輸出值為2

n=2時，A[2]=B[2]=C[2]=D[2]=E[2]=F[2]=4

n>=3時，則可利用上值進行遞推，注意題目對大值取模，此時數(shù)值還是取long類型防止計算過程中發(fā)生數(shù)值溢出的情況

代碼如下：

import java.util.Scanner;public class Main {	static int n;	static long ans, arr1[], arr2[], arr3[], arr4[], arr5[], arr6[];	static long num = 1000000007;	public static void main(String[] args) {		// TODO Auto-generated method stub		Scanner reader = new Scanner(System.in);		n = reader.nextInt();		if (n == 1)			System.out.PRintln(2);		else {			arr1 = new long[n + 1];			arr2 = new long[n + 1];			arr3 = new long[n + 1];			arr4 = new long[n + 1];			arr5 = new long[n + 1];			arr6 = new long[n + 1];			arr1[2] = 4;			arr2[2] = 4;			arr3[2] = 4;			arr4[2] = 4;			arr5[2] = 4;			arr6[2] = 4;			ans = 0;			for (int i = 2; i < n; i++) {				arr1[i + 1] = (2 * (arr1[i] + arr2[i] + arr6[i])) % num;				arr2[i + 1] = (2 * (arr2[i] + arr3[i] + arr5[i])) % num;				arr3[i + 1] = (2 * arr2[i]) % num;				arr4[i + 1] = (2 * arr6[i]) % num;				arr5[i + 1] = (2 * arr5[i]) % num;				arr6[i + 1] = (2 * (arr4[i] + arr5[i] + arr6[i])) % num;			}			ans = arr1[n] + arr2[n] + arr3[n] + arr4[n] + arr5[n] + arr6[n];			ans = ans % num;			System.out.println(ans);		}	}}