試題 歷屆試題 格子刷油漆
【資源限制】 時間限制：1.0s 記憶體限制：256.0MB問題描述
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
解題思路
在矩形的長度大于2的時候有兩種情況： 1.從兩邊上的四個格子開始出發 2.從中間開始出發首先分析第一種情況（從兩邊上的四個格子開始出發）：
(由于四個格子都在最邊上，沒有差別，因此分析一個格子的所有情況乘以4即可得到從邊上出發的情況總和，) 從最邊上走有三種走法：（方式是我胡寫的）①不回頭式
把本列都走過再走下一列
比如此圖，從A開始出發，先走B，再走下一列，走到第二列的路線有兩種，在i等于1的時候只有A到B一種走法，當i等于2的時候，i有1*2種走法，i等于3的時候有1*2*2種走法
由此推出當在第i列的時候有a[i] = 2*a[i-1];
②回傳式
每次先走下一列，最后回傳到開頭相對的格子
比如上兩個圖 從A點出發先到達C點或者D點 所以有b[i] = 2*b[i-1] (由于此方式能回傳到開始格子的對面，所以單獨作為一種方式存盤，在后面能用到)
③一步一回頭式
先走下一列，再回傳上一列，再回傳下一列的對面，然后再訪問下一列
類似于上圖這樣子兩種方式，然后到達E , F 自然有兩種方式，所以推出 a[i] = 2*2*a[i-2]
所以第一種情況得出結論：a[i] = 2*a[i-1]+2*b[i-1]+4*a[i-2]
開頭說過分析一個點，所以把四個點的都加起來就是 sum1 = 4*a[n] //n代表列數
第二種情況（從中間格子開始出發）:
(此情況必須應用在N大于2的時候) 當從中間走的時候就將矩形分成了兩部分，有先從左走和先從右走的區別（排列方式不一樣） 無論先從左走還是先從右走，先走的那一個方向必須能回傳到當前格子的相對的格子，如果不能就回傳不了了 這種方法我在上面提過，就是存盤為b[i]的陣列 從左邊先走有兩種方式（比如從A走）A -> C 和 A -> D兩種
從A出發，最終到達B ，上面已經分析過 ， 有b[i]種方法
然后分析從E或者F走，從E或F走可以回頭式的走，也可以一步走到頭，跟從最邊上點開始走的方式相同，此處避免冗余不再舉例，不懂得可以再翻到頭看，所以有a[n-i]種方法，
在第i列也可以從B走，與A走情況相同，結果乘以2即可，從B到E和F有兩種方法，所以結果也要乘以2
因此總的走法有 2*2*(b[i]*a[i-1])
從右先走，與從左走是相顛倒的
從A往右走，最侄訓傳B，有b[n-i+1]種方法，也可以從B出發，最侄訓傳A，最終結果要乘以2
從B往左走有兩種方法，到達D或C，所以結果也要乘以2
從E或F向左走，有a[i-1]種方法
所以從右先走右有2*2*（b[n-i]*a[i-1]）種走法
從左先走與從右先走加起來就是sum2 = 4*（b[i]*a[i-1]+b[n-i]*a[i-1]）
所以最終結果是sum1+sum2 = 4*a[n]+ 4*（b[i]*a[i-1]+b[n-i]*a[i-1]） 由于
a[i-2] 的結果 所以要給a[1]和a[2]賦值 從a[3]開始算，求a[3] 的時候需要求得b[2]，所以要給出a[1]、a[2]、b[1]、b[2]
當n a[1] = 1 , b[1] = 1 (實際為0，因為只有1列，沒法算，這里改為1，是便于理解，實際沒影響)
當n等于2的時候，只有從四個點開始的情況，所以羅列出來 a[2] = 6 , b[2] = 2;
代碼：
1 import java.util.Scanner; 2 3 public class 格子刷油漆 { 4 public static void main(String[] args) { 5 int Mod = 1000000007; 6 long[] a = new long[1001]; 7 long[] b = new long[1001]; 8 Scanner scanner = new Scanner(System.in); 9 int N = scanner.nextInt();//列數 10 a[1] = 1; 11 b[1] = 1; 12 a[2] = 6; 13 b[2] = 2; 14 if (N==1) { 15 System.out.println("2"); 16 } 17 if (N==2) { 18 System.out.println(a[2]*4); 19 } 20 for (int i = 3; i <=N; i++) {//從頭出發 21 a[i] = (2*a[i-1]+2*b[i-1]+4*a[i-2])%Mod; 22 b[i] = (2*b[i-1])%Mod; 23 } 24 long sum = 4*a[N]%Mod; 25 for (int i = 2; i < N; i++) {//從中間出發，在2到N-1之間 26 sum+=4*(b[i]*a[N-i]%Mod+b[N-i+1]*a[i-1]%Mod)%Mod; 27 sum%=Mod; 28 } 29 System.out.println(sum); 30 } 31 }View Code
致謝
思路借鑒CSDN博主 醬懵靜 https://blog.csdn.net/the_ZED/article/details/104724184
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71898.html
標籤：其他
上一篇：windows下全域配置maven出現is not a directory on the Jenkins master (but perhaps it exists on some agents)