程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
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. 下一頁:
Copyright © 程式師世界 All Rights Reserved