HDU 1143 Tri Tiling（递归）-白红宇

HDU 1143 Tri Tiling（递归）

阅读量：4565 次

发布时间：2019-06-08

本文共 881 字，大约阅读时间需要 2 分钟。

意甲冠军：一些现有的1*2小盒子。求拼3*n多少个长方形的拼写。

思考：

因为它是一个递归式。肯定会遇到层的关系。仔细观察，研究发现，每层应设置2一层。（奇数层不能是矩形）而从显卡好最后一层的最后一战，可以发现。只有两种结果（）。

即：。结果二能够==上一层的结果一和结果二两种结果（非常明显。不多说，用笔画一下便知）。结果一能够==2*（上一层的结果一和结果二）以及结果一。为什么呢？上一层的两种结果都能够分别衍生出1和2两种情况。即2*（上一层的结果一和结果二）。而假设上一层为结果一的话又可另外延伸出一种3情况（上面结果一的对称也一样仅仅能延伸一种。不影响结果）。到这里递推式就出来了。

假设看了两边没弄清的，请按三种情况画个图。第三种为第一种的对称。

代码：

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;int dp[31][2];int main(){ int n; dp[0][0]=1;//这一种情况我非常无语，wa了之后实在找不出错试出来的 dp[2][0]=1;dp[2][1]=2; for(int i=4;i<=30;i++) { dp[i][0]=dp[i-2][0]+dp[i-2][1]; dp[i][1]=3*dp[i-2][1]+2*dp[i-2][0]; } while(~scanf("%d",&n)&&n!=-1) { printf("%d\n",dp[n][0]+dp[n][1]); } return 0;}

转载于:https://www.cnblogs.com/gcczhongduan/p/4804024.html

你可能感兴趣的文章