hdu 2045

容易でないシリーズの(3)——LELEのRPG難題
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 40859    Accepted Submission(s): 16364
Problem Description
「AC女の殺し屋」と呼ばれるスーパーアイドルのLELEは最近、急に深く遊び始めた.
1列に並ぶn個の格子があり、赤(Red)、ピンク(Pink)、緑(Green)の3色で各格子を塗り、各格子に1色塗り、隣接する格子が同色でないことを要求し、しかも首尾両格子も異なる色である.すべての要求を満たす塗り方を求める.
以上が有名なRPGの難題である.
もしあなたがColeだったら、あなたはきっとLELEを助けてこの問題を解決したいと思います.そうでなければ、多くのきれいな痛くて生きたくないCole女のメンツを見ても、あなたは手をこまねいて傍観しないでしょう.
 
Input
入力データは複数のテストインスタンスを含み、各テストインスタンスは1行を占め、1つの整数Nからなる(0 
Output
各試験例について、要求を満たすすべての塗布方法を出力し、各例の出力が1行を占めます.
 
Sample Input

   
   
   
   

    
    
    
    1
2
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
6
   
   
   
   
   
   
   
   


   
   
   
   

出会った問題と解題の構想:
       この問題は、言っても恥ずかしくて、自分で書こうと思っていたのに、馬鹿な1時間半も書いていませんでしたが、入門したばかりなので、ゆっくりしましょう.
       最初は1 2 3 4 5の数を列挙して法則を探すのが自分の考えだった.この様子が馬鹿げていることに気づいて、ずっとできなかった.(個人的には自分の推理の仕方に問題があると感じていますが、大神たちはきっと公式で押しているに違いありません.私は数字で法則TATを探しています)
      それから杭電の上の他の人の問題解を見て、とても良いと感じました.まず、最初の2つの色が違うので、前の1つがどんな色(すなわちf(n-1))なのかを見てみましょう.f(n-1)では、2つの色と首が異なり、1つは同じで、同じように前のf(n)に変化するのがf(n-1)で、それから首と異なるのが2つあり、この2つはf(n-2)のと首と同じで決定され、2つの変化の方式があるため、2*f(n-2)であるため、関係式が出てくる.
      そうだ、longlongを忘れてはいけない.さもないとintの範囲を超えてしまう.
コードを入力:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
 using namespace std; int n; long long a[60]; int main(){
    a[1] = 3;
    a[2] = 6;
    a[3] = 6; for(int i = 4;i < 55;i++){
        a[i] = a[i-1]+ 2 * a[i-2]; } while(scanf("%d",&n)!=EOF){
        printf("%I64d
",a[n]); } return 0; }