Fence Repair POJ 3253 - c++编程基础

?解题思路：本题利用霍夫曼编码的原理解决。这道题本可以用动态规划来解决，之前已经在UVa10003上做过了这道题，不过今天才发现原来就是霍夫曼编码的变形，真的是非常巧妙。我们考察切木棍这个过程可以发现，实际上这把总长为L的木棍切割为L1，L2，L3等等我们需要的木棍是一个树状结构。那么最终的总开销就是sum{木板的长度*节点的深度}。从最优的角度考虑，最短的板对应的深度应当最低。这其实就是霍夫曼编码的原理。而这一过程可以简洁地利用优先队列解决。

?代码：

#define _CRT_SECURE_NO_WARNINGS 
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  #include
                 
                   using namespace std; typedef long long LL; #define N 20000+10 int d[N]; int n; LL ans; void solve() { priority_queue
                  
                   , greater
                   
                     >q; for (int i = 0; i < n; i++) q.push(d[i]); while (q.size()>1) { int l1, l2; l1 = q.top(); q.pop(); l2 = q.top(); q.pop(); ans += l1 + l2; q.push(l1 + l2); } printf(%lld , ans); } int main() { //freopen(t.txt, r, stdin); while (~scanf(%d, &n)) { for (int i = 0; i < n; i++) cin >> d[i]; solve(); } return 0; }