[TIOJ][DP] 1354 池塘裡的青蛙

池塘裡的青蛙

Time Limit:1000MS  Memory Limit:65536K
Total Submit:256 Accepted:149

Description

池塘中有一隻青蛙在四塊石頭A、B、C、D之中跳來跳去。今青蛙由A起跳，每次跳到另一塊石頭，青蛙跳了n次後停在A的方法數有多少呢？

Input

第一行有一數字T，代表輸入含有幾筆測試資料
每筆測試資料含有一行一個數字，代表題目中的n 

Output

請對於每筆資料輸出一行一個數字，代表青蛙跳了n次後停在A的方法數有多少。

Sample Input

2
1
2

Sample Output

0
3

Source

快樂暑假營第一次練習比賽。Problem Setter：hallogameboy
--------------------------------------------------------------------------------------------------------
#include<stdio.h>
int s[1000005][5]={0};
int main(){
    int i,j,k,n,t;
    s[0][0]=1;
    for(i=1;i<=1000005;i++){
        for(j=0;j<4;j++)
            s[i][j]=0;
        for(j=0;j<4;j++)
            for(k=0;k<4;k++)
                if(j!=k)
                    s[i][j]+=s[i-1][k];
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf("%d\n",s[n][0]);
    }

}