【题解】POJ3253

题目大意就是给出n个不同长度的木板，要求将一条整的木板分割成这n个小木板。每次分割的cost就是【分割成的两个子木板】的长度相加。

这个问题我们可以反向思考：把切成的小板子，拼成一块大板子的cost。那么，我们每次拼接，都会产生一个cost。贪心的思路就很明显了，尽可能的让小板子参与更多次的拼接，大板子尽可能少拼接。这样才能使得cost最小。

我们可以用一个小元素在前的优先级队列去实现它，每次取最小的两个板子，把他们拼接起来，计算cost,然后重新加入优先级队列。

代码：

#include<iostream>
#include<queue>
using namespace std;
#define MAXN 20005

typedef long long ll;

int n;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    //声明小的在前面的优先级队列
    priority_queue<int, vector<int>,greater<int> > q;

    cin>>n;

    int tmp;
    for(int i=0;i<n;++i)
    {
        cin>>tmp;
        q.push(tmp);
    }

    ll ans=0;
    int a1,a2, new_plank;
    while(q.size()>1)
    {
        a1 = q.top();
        q.pop();
        a2 = q.top();
        q.pop();

        new_plank = a1+a2;
        q.push(new_plank);
        ans+=new_plank;
    }

    cout<<ans<<endl;

}

转载请注明来源：https://www.longjin666.top/?p=1096

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~