HDU 2045 不容易系列之(3)—— LELE的RPG難題

HDU 2045 不容易系列之(3)—— LELE的RPG難題

思路：

1.若前n-1位塗的顏色是符合條件的，則由於首尾不同，再添加一位時，只有1種方法；即s[n] = s[n-1]

2.若前n-1位組成的串不符合，再添加一位後合法，即因為首尾相同而引起的不合法，那麼前n-2位組成的串必定合法。此時第n位有2種添加方法。即s[n] = 2*s[n-2]

所以AC代碼：

#include
int main()
{
    int n,i;
    __int64 a[55];
    a[1]=3;
    a[2]=6;
    a[3]=6;
    for(i=4;i<=50;i++)
        a[i]=a[i-1]+2*a[i-2];
    while(scanf("%d",&n)!=EOF)
    {
        printf("%I64d\n",a[n]);
    }
    return 0;
}