hdu 2045 쉽 지 않 은 시리즈 (3) - LELE 의 RPG 난제 (전달)

쉽 지 않 은 시리즈 (3) - LELE 의 RPG 난제
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 30045    Accepted Submission(s): 12072
Problem Description
'AC 걸 킬러' 라 불 리 는 슈퍼 아이돌 LELE 가 최근 에 갑자기 심각 한 게임 을 하 게 되 었 다. 이 때문에 많은 '콜' (LELE 의 팬, 즉 '콜라') 이 초조해 졌 다. 여러 가지 탐색 을 통 해 한 베테랑 콜 이 이 유 를 알 게 되 었 다. 알 고 보 니 LELE 는 최근 에 유명한 RPG 난 제 를 연구 하기 시작 했다.
한 줄 로 늘 어선 n 개의 격자 가 있 습 니 다. 빨간색 (빨간색), 분홍색 (Pink), 녹색 (Green) 세 가지 색 으로 각 칸 을 바 르 고 한 칸 에 한 색 을 바 르 며 인접 한 격자 가 같은 색 이 되 지 않도록 요구 합 니 다. 그리고 머리 와 꼬리 두 칸 도 서로 다른 색 입 니 다. 모든 요 구 를 만족 시 키 는 칠 법 을 구 합 니 다.
이상 은 유명한 RPG 난제 입 니 다.
만약 당신 이 Cole 이 라면, 나 는 당신 이 반드시 어떻게 든 LELE 가 이 문 제 를 해결 하도록 도와 줄 것 이 라 고 생각 합 니 다.그렇지 않 았 다 면, 예 쁘 고 죽 고 싶 은 콜 녀 들 을 봐 서 라 도 가만히 있 지 는 않 았 겠 지?
 
Input
입력 데 이 터 는 여러 개의 테스트 인 스 턴 스 를 포함 하고 모든 테스트 인 스 턴 스 는 한 줄 을 차지 하 며 하나의 정수 N 으로 구성 되 어 있 습 니 다. (0 < n < = 50)
 
Output
모든 테스트 인 스 턴 스 에 대해 서 는 요 구 를 만족 시 키 는 도장 법 을 출력 하 십시오. 모든 인 스 턴 스 의 출력 은 한 줄 을 차지 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
    1
2
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
6
   
   
   
   

 
칠 한 n - 1 칸 에 마지막 으로 칸 을 하나 더 넣 으 면 n 칸 을 얻 을 수 있 습 니 다.n - 1 칸 을 채 웠 기 때문에 두 칸 마다 색깔 이 다 릅 니 다.그래서 한 가지 색상 만 삽입 할 수 있 습 니 다.n - 1 칸 은 모두 F [n - 1] 의 메 우 는 방법 이 있다.그래서 n - 1 칸 에서 n 칸 까지 F (n - 1) 방법 이 있 습 니 다.
만약 에 n - 1 이 합 법 적 이지 않 고 하 나 를 추가 한 후에 합 법 적 인 것 으로 바 뀌 면 n - 2 개 는 합 법 적 이 고 n - 1 개 는 첫 번 째 와 같다 (다른 사람 에 게 서 분석).

#include<iostream>
#include<cstdio>
using namespace std;

__int64 a[55];

int main()
{
    a[0]=0;
    a[1]=3;
    a[2]=6;
    a[3]=6;
    int i;
    for(i=4; i<54; i++)
        a[i]=a[i-1]+2*a[i-2];
    int n;
    while(cin>>n)
    {
        cout<<a[n]<<endl;
    }
    return 0;
}