程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Fence Repair POJ 3253

Fence Repair POJ 3253

編輯：C++入門知識

Fence Repair POJ 3253


 

 解題思路：本題利用霍夫曼編碼的原理解決。這道題本可以用動態規劃來解決，之前已經在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;
}

 

  1. 上一頁:
  2. 下一頁:
C++入門知識
C++ 拷貝構造函數

作者 ： 卿笃軍 1）定義：拷貝構造函數，是一種特
LeetCode 148:Sort List

LeetCode 148:Sort List Sort a

POJ 3009 Curling 2.0 求解！

 Descriptio
數組的定義和初始化，數組定義初始化

數組的定義和初始化，數組定義初始化一、定義 數組的維數必須用
HDU-1542-Atlantis-線段樹+面積並（模板）

HDU-1542-Atlantis-線段樹+面積並（模板）

前置和後置運算符

這是迅雷一問一答的題目： [cpp]  #i
相關文章
閱讀排行榜
HDU 4407 Sum（12年金華網絡賽-容斥原理） 基本排序系列之基數排序 poj 3280 區間dp POJ 2536 二分匹配 匈牙利算法 || 網絡流 11589 - Save the President（暴力+技巧枚舉） c++引用學習 論C/C++函數間動態內存的傳遞 ACM非前綴編碼 C++實現 異步更新界面方法 深入探索spring技術內幕(一): spring概述 飯卡（HDOJ2546）
熱門圖文
java監聽-java中匿名類作為一個方法的參數的時候是不是默認返回一個匿名對象 C++同步串口通信 C語言學習教程第十章-文件(7) asp中設置session過期時間方法總結 3611: [Heoi2014]大工程|樹形DP|虛樹 javascript-點擊超鏈接後新頁面沒加載js php查詢mysql大量數據造成內存不足的解決方法 pageEncoding與contentType屬性，pageencoding
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved