| Description |
|
hero为了能顺利娶princess ，花了血本，买了个房子，现在决定装修。房子的长度为n米，宽度为3米，现在我们有2种地砖，规格分别是1米×1米，2米×2米，如果要为该教室铺设地砖，请问有几种铺设方式呢 1 /* 2 *这道题我着实卡了挺长时间的，今天翻出来一看最开始以为是DP，原来不是DP， 3 *是组合数学里面的问题，然后我害怕超范围特意写了个c[m][n]=c[m][n-1]+c[m-1][n-1] 4 *递推。 5 *然后还是没过，因为我开始写的是res+=c[i][n-i]*2； 然后我怎么想都对。 6 *后来我发现这么搞是不对的，应该是*2^i的。改了就AC了！挺有成就感的！加油！ 7 */ 8 #include <iostream> 9 using namespace std; 10 int c[35][35]; 11 void haha() 12 { 13 int i,j; 14 for(i=1;i<=30;++i) 15 { 16 c[i][i]=1; 17 c[1][i]=i; 18 } 19 for(i=2;i<=30;++i) 20 { 21 for(j=i+1;j<31;++j) 22 { 23 c[i][j]=c[i][j-1]+c[i-1][j-1]; 24 } 25 } 26 return; 27 } 28 int A(int n) 29 { 30 int i; 31 long long res=1; 32 for(i=1;i<=n;++i) 33 res*=2; 34 return res; 35 } 36 int main() 37 { 38 haha(); 39 int n,i,j,t; 40 long long res; 41 while(cin>>t) 42 { 43 while(t--) 44 { 45 res=1; 46 cin>>n; 47 for(i=1;i<=n/2;++i) 48 { 49 res+=c[i][n-i]*A(i); 50 } 51 cout<<res<<endl; 52 } 53 } 54 return 0; 55 } 56 57 58 |