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

題目

用遞歸

現在考慮n>3的情況，

若第n-1個格子和第一個格子不同，則有f(n-1)種情況；

若第n-1個格子和第1個格子相同，則第n-2個格子和第一個格子必然不同，此時為f(n-2)再乘第n-1個格子的顔色數，很顯然第n-1個格子可以是第一個格子（即第n-2個格子）的顔色外的另外兩種，這樣為2*f(n-2)；

是以總的情況為f(n)=f(n-1)+2*f(n-2);

#include <stdio.h>
int main()
{
int a,i;
double s[51];  在百度上檢視他人代碼的時候，發現他們用的都是_int a[51],輸入用的是：%I64d，然而我用的是int結果WA了，然後換成double就可以了
s[1]=3;
s[2]=6;
s[3]=6;
for(i=4;i<=50;i++)
{
s[i]=s[i-1]+2*s[i-2];
}

while(~scanf("%d",&a))
{
printf("%.lf\n",s[a]);
}

return 0;
}