Tri Tiling

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3004 Accepted Submission(s): 1687

Problem Description

In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.

Input

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤ n ≤ 30.

Output

For each test case, output one integer number giving the number of possible tilings.

Sample Input

-1

Sample Output

153

2131

Source

University of Waterloo Local Contest 2005.09.24

思路详见：动态规划

我的代码：

const int maxn = ;

int dp[maxn][];

void init() {

    dp[][] = dp[][] = ;

    dp[][] = ;

    dp[][] = dp[][] = ;

    dp[][] = ;

    for (int i = ; i <= ; i ++) {

        dp[i][] = dp[i-][] + dp[i-][] + dp[i-][];

        dp[i][] = dp[i-][];

        dp[i][] = dp[i-][] + dp[i][];

    }

}

int main() {

    int n;

    init();

    while (~scanf("%d", &n)) {

        if (n == -) break;

        printf("%d\n", dp[n][]);

    }

    return ;

}

Discuss里的代码：

const int MAX=;

int s[MAX];

int main()

{

    int i,n;

    s[]=;

    s[]=;

    for(i=;i<MAX;i+=)

    {

        s[i]=*s[i-]-s[i-];

    }

    while(cin>>n,n>=)

    {

        if(n&)

            cout<<<<endl;

        else

            cout<<s[n]<<endl;

    }

    return ;

}

巴特西

HDU1143（3N的地板铺12的砖）

Tri Tiling

最新文章

热门文章

巴特西

HDU1143（3*N的地板铺1*2的砖）

Tri Tiling

最新文章

热门文章

HDU1143（3N的地板铺12的砖）