考虑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[1]=3; z[2]=9; for(int i=3;i<=40;i++) z[i]=2*z[i-1]+z[i-2]; int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); printf("%lld\n",z[n]); } return 0; }
原文：http://www.cnblogs.com/cherryMJY/p/6238234.html