hdu 2045 不容易系列之(3)—— LELE的RPG难题

解题思路：

f(n)=1,2,.....n-2,n-1,n

前n-2个已经涂好，那么n-1有两种可能

1.n-1与n-2和1 的颜色都不同

1 粉,   n-2 红,   n-1 绿、  那么n的颜色可以说是没得选了f(n-1)种可能

1 红,   n-2 绿 ,   n-1 粉

1 绿,    n-2 红,    n-1 粉

2.n-1与n-2不同但与1相同，那么n就有两种选择

1 红,   n-2 绿,   n-1  红,   n 绿/粉

1 绿,   n-2 粉,   n-1  绿,   n 粉/红

1 粉,    n-2 红,    n-1 粉   n 红/绿

可以看出此时 n的颜色可能有2*f(n-2)

#include <stdio.h>

int main(void)

{

    int n,i;

    long long larr[55];

    larr[1]=3;larr[2]=6;larr[3]=6;

    for(i=4;i<55;i++)larr[i]=larr[i-1]+2*larr[i-2];

    while(scanf("%d",&n)!=EOF)

        printf("%lld\n",larr[n]);

    return 0;

}