TCO14 1B L3: EagleInZoo, dp，tree - c++编程基础

TOP

TCO14 1B L3: EagleInZoo, dp，tree

2015-07-20 17:52:58 来源: 作者: 【大中小】浏览:2次

看到树，又是与节点有关，一般是dp，dp[v][t] 表示在以v为root的subtree上有t个eagle时满足条件的概率。一个注意点是求二项系数数组C[]时，因为值太大，要用double，不能用long long, long long 会溢出。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include
                 #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) typedef pair
                        
                          pii; typedef long long llong; typedef pair
                         
                           pll; #define mkp make_pair /*************** Program Begin **********************/ const int MAX_N = 51, MAX_K = 101; double dp[MAX_N][MAX_K]; double C[MAX_K][MAX_K]; // 二项系数，注意：用 long long 会溢出 class EagleInZoo { public: vector < vector
                          
                            > childs; double rec(int v, int t) { if (1 == t) { return 1.0; } double & res = dp[v][t]; if (res > -0.5) { return res; } if (childs[v].size() == 0 && t > 1) { // 该节点无 child 且t > 1，最后一只一定无法停留 res = 0; return res; } res = 0; for (int i = 0; i < childs[v].size(); i++) { int x = childs[v][i]; int c = childs[v].size(); for (int j = 0; j <= t - 2; j++) { res += (1.0 / c) * C[t-2][j] * pow(1.0 / c, j) * pow( 1.0 * (c-1) / c, t-2-j) * rec(x, j + 1); } } return res; } double calc(vector 
                           
                             parent, int K) { for (int i = 0; i < MAX_N; i++) { for (int j = 0; j < MAX_K; j++) { dp[i][j] = -1.0; } } childs.resize(parent.size() + 1); for (int i = 0; i < parent.size(); i++) { childs[ parent[i] ].push_back(i + 1); } // calculate C[] C[0][0] = 1; for (int i = 1; i <= K - 1; i++) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; j++) { C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; } } return rec(0, K); } }; /************** Program End ************************/


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：c++模板的一些语法	下一篇：HDU 1698 Just a Hook（线段树成..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: