hdu  1143

http://acm.hdu.edu.cn/showproblem.php?pid=1143

Tri Tiling

In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle.

  
  

   
   2
8
12
-1
  
  

  
  

   
   3
153
2131
  
  

当n为奇数的时候是不能用2*1的方块摆满的，所以f[i] = 0;

当n为偶数的时可以这样划分，2和f[n-2]，则有2*f[n-2]种，4和f[n-4]但是4的部分不能分解为2,2否则的话就跟2和f[n-2]这种情况重复了，在这种情况下只有两种摆法；接着是6和f[n-6]，8和f[n-8].................f[0],这些情况都只有2种摆法。

递推方程f[n] = f[n-2]*f[2]+2*(f[n-4]+f[n-6]+f[n-8]............+f[0]);

#include <iostream>
#include<string>
#include<string.h>
using namespace std;

int main()
{
    int f[32] ;
    f[0] = 1 ;
    f[2] = 3 ;
    f[1] = 0 ;
    for(int i = 3  ; i<= 31 ; i++){
        if(i &1)
            f[i] = 0 ;
        else{
             f[i] = f[i -2] * f[2] ;
             int j = i - 4 ;
             while(j >= 0){
                f[i] += f[j]*2 ;
                j -= 2 ;
             }
        }

    }
     int n ;
     while(cin>>n )  {
        if(n == -1)
        break ;
        cout<< f[n]<<endl;
     }
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1207

汉诺塔II

  
  

   
   1
3
12
  
  

  
  

   
   1
5
81
  
  

解题思路：

对于i个盘子，从1到i进行枚举（变量设为j），将j个盘子移动到第四个柱子上，对于剩下的盘子，则可看成是三个柱子下的情况，枚举过程中找到一个最小值即为此时i个盘子的最小移动次数。注：三个柱子情况下，n个盘子需要移动2^n-1次

#include <iostream>
#include<string>
#include<string.h>
using namespace std;

int main()
{
    double a3[65] ;
    double f4[65] ;
    int i  , j ;
    a3[1] = 2 ;
    f4[1] = 1 ;
    for(i = 2 ; i < 65 ; i++)
        a3[i] = 2 * a3[i - 1] ;
    for(i =  1 ; i < 65 ; i++)
        a3[i] -= 1 ;
    for(i = 1 ;  i < 65  ; i++){
        double mmin= a3[i] ;
        double temp ;
        for(j = 1 ;  j < i ; j ++){
            temp = a3[i - j] + 2 * f4[j] ;
            if(temp < mmin)
                mmin = temp ;
        }
        f4[i] = mmin ;
    }

     int n ;
     while(cin>>n )  {

        cout<< f4[n]<<endl;
     }
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1249

三角形

  
  

   
   2
1
2
  
  

  
  

   
   2
8
  
  

<span style="background-color: rgb(255, 255, 255);">int main()
{
    int f[10004] ;
    f[1] = 2 ;
    for(int i = 2 ;  i < 10001 ; i++)
        f[i] = f[i - 1] + 6 * (i  -1 )  ;
     int  t  , n;
     cin>> t  ;
     while(t-- )  {
        cin >> n ;
        cout<< f[n]<<endl;
     }
    return 0;
}</span>

hdu 1267

http://acm.hdu.edu.cn/showproblem.php?pid=1267

下沙的沙子有几粒？

  
  

   
   1 1
3 1
  
  

  
  

   
   1
3
  
  

公式为

a[n][m] = a[n-1][m] +a[n][m-1]

此二维中，n是记录的H，m记录的是D

而a[n-1][m]代表的是a[n][m]以D结尾时，则前面就是a[n-1]的数目

同理a[n][m-1]也是一个意思

int main()
{
    int m ,  n ;
    long long a[23][23] ;
    memset(a , 0 , sizeof(a)) ;
    for(int i =1 ; i <= 20 ; i++)
        a[i][1] = i ;
    for(int i = 2 ; i <= 20 ; i++){
        for(int j = 2 ;  j<= i ; j++)
            a[i][j] = a[i][j - 1] + a[i -1][j] ;
    }
     while(cin>>m>>n )  {
        cout<< a[m][n]<<endl;
     }
    return 0;
}

   
   

    
    1
2
3
   
   

   
   

    
    2
4
8
   
   

f(n) = (n * n + 5 ) *n  / 6 + 1 ;

int main()
{
   int n ;
     while(cin>>n )  {
           int  s = (n * n + 5 ) *n  / 6 + 1 ;
        cout<<  s<<endl;
     }
    return 0;
}

最后

以上就是清新路人最近收集整理的关于hdu 递推 Tri Tiling 汉诺塔II 三角形 下沙的沙子有几粒？ 献给杭电五十周年校庆的礼物的全部内容，更多相关hdu内容请搜索靠谱客的其他文章。