|
問題描述
X國(guó)的一段古城墻的頂端可以看成 2*N個(gè)格子組成的矩形（如下圖所示）,，現(xiàn)需要把這些格子刷上保護(hù)漆。 你可以從任意一個(gè)格子刷起,，刷完一格,，可以移動(dòng)到和它相鄰的格子（對(duì)角相鄰也算數(shù)），但不能移動(dòng)到較遠(yuǎn)的格子（因?yàn)橛推嵛锤刹荒懿龋,。?br>
比如：a d b c e f 就是合格的刷漆順序,。 輸入格式
輸入數(shù)據(jù)為一個(gè)正整數(shù)（不大于1000）
輸出格式
輸出數(shù)據(jù)為一個(gè)正整數(shù),。
樣例輸入
2
樣例輸出
24
樣例輸入
3
樣例輸出
96
這道題,，根據(jù)數(shù)據(jù)量便可得知，使用的算法應(yīng)該是動(dòng)態(tài)規(guī)劃,，難點(diǎn)在于需要從第一個(gè)刷漆的格子的位置,，將整體分成左右兩半， 先刷一半,，再刷另一半
dp[i][0]表示從第i個(gè)格子出發(fā),，刷滿前i個(gè)格子后，最后回到第i個(gè)格子的方法數(shù),， dp[i][1]表示從第i個(gè)格子出發(fā),，刷滿前i個(gè)格子后沒有回到第i個(gè)格子的方法數(shù)。
下面是我的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 //此處累加遍歷第一個(gè)被刷的格子的列 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 } 測(cè)評(píng)結(jié)果：
|
|
|
