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

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;
}

 

  1. 上一頁:
  2. 下一頁:
關於C++
leetcode_6_ZigZag Conversion

描述: The string PAYPALISHIRIN
Behavioral模式之State模式

1.意圖允許一個對象再其內部狀態改變時，改變它的行為。對象看
寫時拷貝的方式實現C++中string類

一、寫時拷貝的引入 class String{ f
解析動態聯編(下篇)

三 虛函數表VTABLE動態聯編過程跟我們猜測
hdu5301(2015多校2)

 BuildingsTime Limit: 400
圖解VC++2012編譯安裝GDAL1.11.0和入門例子

相關下載     http://pan.
相關文章
閱讀排行榜
在C++Builder中使用Delphi文件 LeetCode Valid Number LeetCode242——Valid Anagram POJ 3126 Prime Path( 廣搜 ) BNUOJ 1038 Flowers(BFS) BZOJ 4025 二分圖 分治+並查集 hdu 1142 A Walk Through the Forest (digkstra+記憶化搜索) 【poj 2411】Mondriaan&#39;s Dream 狀態壓縮DP Eclipse CDT使用GDB調試C++的問題:無源文件命名(No source file named) 1049. Counting Ones (30)[計算1 的個數]——PAT (Advanced Level) Practise [LeetCode] Game of Life
熱門圖文
php Rename 更改文件、文件夾名稱 UVALive 6916---Punching Robot(盧卡斯+容斥)，uvalive Delphi在MDI窗口中顯示圖形控件及指定背景的解決方案 JSP報表打印的一種簡單解決方案 Python中的lstrip()方法使用簡介 php數組練習之----查詢數組中某key的鍵值相同的個數、數組的格式轉換、合並數組 DELPHI在局域網中的一則應用 php如何防止圖片盜用/盜鏈的兩種方法，
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved