递推 HDU 2569

考虑n-2 n-1 n

z[n] 代表n个块 可行方案

1  n-2 和n-1 同 3*z[n-2]

2  n-2和n-1不同 2*(z[n-1]-z[n-2]); 减一减 然后可能是其中一种 *2

z[n]=2*z[n-1]+z[n-2];

z[1]=3;
z[2]=9;

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

using namespace std;

typedef long long ll;

#define MAXN 105

ll z[MAXN];

int main()

{

    z[]=;

    z[]=;

    for(int i=;i<=;i++)

        z[i]=*z[i-]+z[i-];

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        scanf("%d",&n);

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

    }

    return ;

}