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

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

 

分析过程：

1）如果前F(N-1)是符合要求的涂发，即N-1和第一位是不同的，则N位只有一种颜色可以用 F(N-1)

2）如果前N-1是不符合要求的 即N-1和第一位相同，则除掉N-1后之前N-2个是符合要求的，这种情况下有N可以有两种涂发 所以 2*F(N-2)

 

发现 F(N) = F(N-1) + 2*F(N-2)

 

因为N<=50

用long类型不行，溢出了，应该用double

 

代码如下：

#include <stdio.h>

int main()
{
    int n,i;
    double a[100];
    a[0]=1;
    a[1]=3;
    a[2]=6;
    a[3]=6;
    for (i=4; i<54; i++) {
        a[i]=a[i-1]+2*a[i-2];
    }
    while (scanf("%d",&n)!=EOF) {
        printf("%.0f\n",a[n]);
    }
    return 0;
    
}