UVa 10918 - Tri Tiling

Problem link

Keyword: DP

Algorithm:

This DP method is a little complex.
First, because of the size of 1 tile, there will be no solution when N%2 = 1.
For each length, there will be 3 * ans[ N-2 ] ways because if N=2, there are 3 solutions.
Next, there will be 2 solutions with size greater than 2 followed by the following pattern:
| -- -- -- ... -- -- -- |
| -- -- -- ... -- -- -- |
-- -- -- ....... -- -- --
As a result, we add 2 * ans[ N-4 ], 2 * ans[ N-6 ], and so on, to the solution.
And that's it.

Code:

#include<cstdio>

int main()
{
    int n, ans[ 31 ] = { 1 };
    for( int i = 2; i <= 30; i += 2 )
    {
        for( int j = i-2; j >= 0; j -= 2 )
            ans[ i ] += ans[ j ] << 1;
        ans[ i ] += ans[ i-2 ];
    }

    while( scanf( "%d", &n ) && n != -1 )
        printf( "%d\n", ans[ n ] );

    return 0;
}