HDU 2569 彼岸

彼岸

思路：动态规划。因为不能有连续三个不同的颜色，所以只要看最后三个就可以了。

设dp[n]为长度为n到达彼岸的方案数。

①当第n-2个颜色和第n-1个颜色相同时，第n个位置可以取任意一种颜色，dp[n-1]==dp[n-2]，dp[n] = dp[n-2]*3;

②当第n-2个颜色和第n-1个颜色不同时，第n个位置只要取前两个中的任意一个即可，dp[n-1]-dp[n-2]为第n-1个位置不同的方案数，dp[n] =（dp[n-1]-dp[n-2]）*2。

dp[n] = dp[n-2]*3 +（dp[n-1]-dp[n-2]）*2 = dp[n-1]*2+dp[n-2]

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset((a),(b),sizeof(a))
const int INF=0x3f3f3f3f;
const int N=1e5+5;
ll dp[40];

int main()
{
    int n;
    int c;
    dp[1]=3;
    dp[0]=3;
    for(int i=2;i<40;i++)
    {
        dp[i]=dp[i-1]*2+dp[i-2];
    }
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d",&n);
        printf("%lld
",dp[n]);
    }
    return 0;
}