ACM 2190 重建希望小学

 

 

分析过程：

考虑第N格，如果N-1排好了，第N只有3个1X1一种排法，如果N-2排好了，有3种排法，有1种在N-1的情况包括了，

所以F(N) = F(N-1) + 2F(N-2)

 

代码如下：

 

#include <stdio.h>

int main()
{
    int n,i,c;
    double a[31];
    a[0]=1;
    a[1]=1;
    a[2]=3;
    for (i=3; i<=30; i++) {
        a[i]=a[i-1]+2*a[i-2];
    }
    
    scanf("%d",&c);
    while (c--) {
        scanf("%d",&n);
        printf("%.0f\n",a[n]);
    }
    return 0;
    
}