HDU 2045 RPG难题

http://acm.hdu.edu.cn/showproblem.php?pid=2045

这道题也是用倒推：

先假设前n-2个块都已经涂好，涂第n-1块时有以下两种情况：

1.n-1和1相同，则n有两种涂法。退回n-2接着推

2.n-1和1不同，则n只有一种涂法，退回n-1接着推

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;


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

}