poj 3253 Fence Repair (优先队列，哈弗曼)

题目链接：http://poj.org/problem?id=3253

题意：给出n块木板的长度L1,L2...Ln，求在一块总长为这个木板和的大木板中如何切割出这n块木板花费最少，花费就是将木板切割前的长度。

有个陷阱就是需要用long long 去储存

如

Sample Input

3
8
5
8

Sample Output

就是将一块长为21的木板先切成13和8，花费21。然后将13切成5和8，花费13，总花费21 + 13 = 34。

分析：如果考虑从一块木板分割成小木板，方法数会有很多种，其实可以转化成从小木板合成大木板。

其实就是构造一棵最优二叉树（哈夫曼树），然后求出这棵树带权路径长度，过程如下：

题目可以转化为Huffman树构造问题：

给定 N planks of woods，

1. 　　在 N planks 中每次找出两块长度最短的木板，然后把它们合并，加入到集合A中，

2.　　在集合中找出两块长度最短的木板，合并加入到集合A中，重复过程，直到集合A中只剩下一个元素

显然，通过每次选取两块长度最短的木板，合并，最终必定可以合并出长度为 Sum（Li）的木板，并且可以保证总的耗费最少

所以采用优先队列，每次都取出两块最短的木板，然后结果加上这两块木板长度，再入队（这两块木板长度之和），直到木板之和为一块

#include<bits/stdc++.h>

const long long maxn = 2e4+;

using namespace std;

int main()

{

    priority_queue<long long,vector<long long>, greater<long long> > q;

    long long n;

    scanf("%lld", &n);

    if(n == )

    {

        long long l;

        scanf("%lld", &l);

        printf("%d\n", l);

        return ;

    }

    if(n == )

    {

        long long l1, l2;

        scanf("%lld %lld", &l1, &l2);

        printf("%d\n",l1+l2);

        return ;

    }

    while(n--)

    {

        long long t;

        scanf("%lld", &t);

        q.push(t);

    }

    long long res = ;

    do

    {

        long long t1 = q.top();q.pop();

        long long t2 = q.top();q.pop();

//        printf("%d %d\n", t1, t2);

        q.push(t1+t2);

        res += t1+t2;

    }while(q.size()!= );

    printf("%lld\n",res);

    return ;

}

巴特西

poj 3253 Fence Repair (优先队列，哈弗曼)

最新文章

热门文章