HDU 2659 彼岸

彼岸"/>

HDU 2659 彼岸

点击打开链接.php?pid=2569

设当悬崖的长度为n时，到达彼岸的方法有F[n]种。

    显然，F[1] = 3, F[2] = 9, F[3] = 21    假设已知F[n-1]与F[n-2]，寻求F[n]与F[n-1]、F[n-2]之间的关系。

    分为两种情况：

    (1)第n-2段与n-1段颜色相同，则第n段可以为三种颜色的任意一种：

    F[n-2] * 3

    (2)第n-2段与n-1段颜色不同，第n段只能为其中的两种颜色：

    (F[n-1] - F[n-2]) * 2

    故，总的方法数为：F[n-2] * 3 +　(F[n-1] - F[n-2]) * 2　＝　F[n-1] * 2 + F[n-2]

#include<stdio.h>
int main()
{int t,i,n;__int64 a[41]={0,3,9,21};for(i=4;i<41;i++){a[i]=2*a[i-1]+a[i-2];}scanf("%d",&t);while(t--){scanf("%d",&n);printf("%I64d\n",a[n]);}return 0;
}