`
believexkx
  • 浏览: 22576 次
  • 性别: Icon_minigender_2
  • 来自: 济南
社区版块
存档分类
最新评论

POJ 3253--Fence Repair

    博客分类:
  • DP
阅读更多
在写这道题之前,先介绍几点知识。
一、动态规划(DP)
动态规划(dynamic programming)是求解决策过程最优化的数学方法。早在20世纪50年代初美国数学家R.E.Bellman等人就提出了著名的最优化原理,把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。

DP是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。由于各种问题的性质不同,确定最优解的条件也互不相同,因为动态规划的设计方法对不同的问题,除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。按道理来说,计算机科学的更新速度是很快的,但现在所学的好多算法都是50年代、70年代的,可见此算法的精髓所在,同时也鼓励大家有自己的想法。

二、
堆有最大堆和最小堆之分,最大堆就是每个节点的值都>=其左右孩子(如果有的话)值的完全二叉树。最小堆便是每个节点的值都<=其左右孩子值的完全二叉树
堆的三种基本操作
⑴最大堆的插入
  由于需要维持完全二叉树的形态,需要先将要插入的结点x放在最底层的最右边,插入后满 
  足完全二叉树的特点;
  然后把x依次向上调整到合适位置满足堆的性质
  时间:O(logn)。
  “结点上浮”
 


⑵删除
  要从大小为n的堆中删除结点a[i]:
  用a[n]来替换a[i];
  堆的大小减1(dec(n));
  把a[i](原a[n])下调到合适位置。//往上已符合堆?
  “结点下沉”



⑶初始化
  方法1:插入法:
  从空堆开始,依次插入每一个结点,直到所有的结点全部插入到堆为止。
  时间:O(n*log(n))
  方法2:调整法:
    序列对应一个完全二叉树;从最后一个分支结点(n div 2)开始,到根(1)为止,依次 
  对每个分支结点进行调整(下沉),以便形成以每个分支结点为根的堆,当最后对树根结点
  进行调整后,整个树就变成了一个堆。
  时间:O(n)








三、哈夫曼树(堆的应用之一)
现在才切到正题,哈夫曼树便是由最小堆来建立的,最小堆中的每一个元素包括一棵二叉树及其权重值。

给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree),当然它满足堆的性质。
先了解几个基本术语:
路径和路径长度
  在一棵树下,从一个结点往下可以达到的孩子或子孙节点之间的通路,称为路径。通路中分        
  支的数目称为路径长度。若规定根节点的层数为1,则从根节点到第L层的路径长度为L-1
结点的权及带权路径长度
  若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径   
  长度为:从根节点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度
  树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL= Σ (wi x li),其中wi是叶子结点的权重,li是从根到该叶子结点的路径长度,注意,带全路径长度只有叶子结点有权重,其他结点只计算长度无权重!
首先先来看看为什么哈夫曼树是最优的二叉树


WPL(a) = 7*2 + 5* 2 + 2*2 +4*2 = 36
WPL(b)=4*2 + 7*3 + 5*3 + 2 = 46
WPL(c) = 7 + 5 * 2 + 3 * 2 + 4 * 3 = 35
所以c是最优二叉树。


POJ 3253这道题的大意是有一个农夫要把一个木板砍成几块给定长度的小木板,每次据都要收取一定费用,这个费用就是据的这个木版的长度,用赫夫曼树的思路,用优先队列实现。逆向思维,每次都把木板拼接,要想每次都花费最少就得取最小的两个木板拼接起来再把拼接好的木板入队。

java 代码:
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	PriorityQueue<Long> qq = new PriorityQueue<Long>(20000);

	void run() {
		Scanner scan = new Scanner(System.in);
		long sum = 0, x, y, temp;
		int n = scan.nextInt();
		for (int i = 0; i < n; i++)
			qq.add(scan.nextLong());
		
		for (int i = 1; i < n; i++) {
			x = qq.poll();
			y = qq.poll();
			temp = x + y;
			sum += temp;
			qq.add(temp);
		}
		System.out.println(sum);
	}

	public static void main(String[] args) {
		new Main().run();
	}
}
  • 大小: 48.5 KB
  • 大小: 53.1 KB
  • 大小: 27 KB
  • 大小: 53.7 KB
  • 大小: 43.2 KB
分享到:
评论

相关推荐

    POJ3253-POJ3253-Fence Repair【STL优先队列】

    标题“POJ3253-POJ3253-Fence Repair【STL优先队列】”指的是一个在线编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。该题目要求参赛者使用C++编程语言解决特定的问题,并且在解决方案中...

    POJ2002-Squares

    【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...

    POJ1426-Find The Multiple【BFS+同余模】

    【标题】"POJ1426-Find The Multiple【BFS+同余模】"是一道来源于北京大学在线编程平台POJ的算法题目,主要涉及到了广度优先搜索(BFS)与同余模运算的知识点。这道题目要求解决的是寻找一个整数的倍数问题,可能...

    POJ1129-Channel Allocation【四色定理】

    标题中的“POJ1129-Channel Allocation”是指一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目涉及到“四色定理”,这是图论领域的一个经典问题。 四色定理是图论中的一个重要...

    POJ3020-Antenna Placement

    【标题】"POJ3020-Antenna Placement"是一个经典的计算机编程竞赛题目,源自北京大学的在线评测系统POJ(PKU Online Judge)。这个题目挑战了参赛者在算法设计和实现上的能力。 【描述】"解题报告+AC代码"意味着这...

    poj 1000 - 2000 部分题目 官方分类

    《POJ 1000 - 2000 部分题目 官方分类》 编程竞赛,特别是在线判题系统(如POJ,即Problem Online Judge)中的题目,是提升编程技能和算法理解的重要途径。POJ 1000 - 2000 是一个涵盖广泛的题目区间,包含了大量的...

    魔兽世界终极版POJ的-测试数据

    这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q

    POJ2299-Ultra-QuickSort

    【标题】"POJ2299-Ultra-QuickSort"是北京大学在线判题系统POJ上的一道编程题目,其主要涉及的算法是快速排序(Ultra-QuickSort)。快速排序是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是采用...

    POJ1837-Balance

    【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...

    POJ1258-Agri-Net【Prim】

    【标题】"POJ1258-Agri-Net【Prim】" 是一个编程竞赛题目,来源于北京大学的在线评测系统POJ(Problem Online Judge)。这个题目主要涉及到图论中的一个重要算法——普里姆(Prim)算法。 【描述】"北大POJ1258-...

    POJ1010-STAMPS

    【标题】"POJ1010-STAMPS"是一个编程题目,来源于北京大学的在线判题系统POJ(Problem Set of Peking University),这是一处训练程序员算法技能和编程能力的平台。该题目旨在考察参赛者对动态规划或贪心算法的理解...

    POJ1523 - SPF 测试数据

    【标题】"POJ1523 - SPF 测试数据"是源于 Greater New York 2000 年编程竞赛中的问题H,这个题目在ACM(国际大学生程序设计竞赛)领域内颇具代表性。SPF全称为Shortest Path First,通常指的是寻找图中最短路径的一...

    POJ3414-Pots

    标题“POJ3414-Pots”是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这个题目主要考察的是算法设计和实现能力,通常涉及计算机科学中的数据结构和算法知识。 解题报告是参赛者在...

    POJ2525-Text Formalization【TrieTree】

    《POJ2525-Text Formalization:深入解析TrieTree》 在计算机科学的世界里,算法和数据结构是解决问题的关键。今天我们要探讨的是一个名为"POJ2525-Text Formalization"的问题,它涉及到一种高效的数据结构——Trie...

    POJ2503-Babelfish

    【标题】"POJ2503-Babelfish"是一个来自北京大学在线判题系统(POJ,Problem Online Judge)的编程题目。该题目要求参赛者编写程序解决特定的算法问题,通过编程语言实现,然后提交代码以供系统自动评测。 【描述】...

    POJ1003-Hangover

    【标题】"POJ1003-Hangover"是一个编程竞赛题目,源自北京大学的在线判题系统POJ(Problem Online Judge)。这类题目通常要求参赛者编写程序来解决特定的算法问题,以此锻炼和测试编程技能及算法理解能力。 【描述...

    POJ1009-Edge Detection

    【标题】"POJ1009 - 边缘检测" 在计算机图形学与图像处理领域,边缘检测是一项至关重要的技术。北京大学编程平台POJ上的第1009题,"Edge Detection"(边缘检测),旨在让学生通过编程实现对图像进行边缘检测。此题...

    POJ1201-Intervals

    【标题】"POJ1201-Intervals" 是北京大学在线编程平台POJ上的一道题目,这道题目主要涉及计算机科学中的算法设计与分析,尤其是数据结构和时间复杂度优化方面的知识。 【描述】"北大POJ1201-Intervals 解题报告+AC...

    POJ3122-Pie

    【标题】"POJ3122-Pie"是一道来自北京大学在线判题系统POJ(Problem Online Judge)的编程题目。这道题目通常被用于训练程序员的数据结构和算法技能,特别是解决数学问题的能力。在编程竞赛或者算法训练中,这类题目...

    POJ1002-487-3279【Hash+Qsort】

    标题中的"POJ1002-487-3279【Hash+Qsort】"是指一个编程挑战题目,通常在在线编程平台上出现,比如北京大学的Peking Online Judge (POJ)。这个题目结合了哈希表(Hash)和快速排序(Qsort)两种算法来解决问题。哈希...

Global site tag (gtag.js) - Google Analytics