POJ - 3253 Fence Repair

题意：要将一个木板分成几个小的木板，每次的费用是当前木板的大小，求得到所有木板的最小花费

思路：利用Huffman思想，采用优先队列

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

struct node{
    long long len;
    bool operator<(const node &a)const{
        return len > a.len;
    }
};
priority_queue<node> s;

int main(){
    int n;
    node a;
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf("%lld",&a.len);
        s.push(a);
    }
    long long ans = 0;
    while (s.size() > 1){
        node x = s.top();s.pop();
        node y = s.top();s.pop();
        x.len += y.len;
        ans += x.len;
        s.push(x);
    }
    printf("%lld\n",ans);
    return 0;
}

POJ - 3253 Fence Repair,布布扣,bubuko.com

POJ - 3253 Fence Repair

原文：http://blog.csdn.net/u011345136/article/details/20284369