【题解】木板【题解】木板

题目描述 Farmer John希望修复围绕农场的一小段围栏。他测量了一下，发现需要N（1≤N≤20000）根木头，每根都有某一个整数长度Li（1≤Li≤50000）单位长度。他买了一根很长的很长的木头，正好能够锯出他所需要的N根木头。（即它的长度正好等于Li的总和）。Farmer John忽略锯口，锯掉的木屑产生的长度损失忽略不计，你也可以忽略它。Farmer John遗憾的发现他自己没有用于切木头的锯子，所以他就带着那根很长的木头来到了Farmer Don的农场，想问他借一个锯子。Farmer Don是一个保守的资本家，他不愿意借锯子给Farmer John，但愿意自己来切这N-1刀，每一次都向FJ收取费用。每次的收费正好等于你要锯的那根木头的总长度。例如，你要锯一根长度为21的木头，就花费21分钱。Farmer Don然后让Farmer John自己决定每次锯木头的顺序和位置。帮助Farmer John确定锯出这N根木头的最小总花费。Farmer John知道可以有很多种不同的切割方式，不同的方式可能得到不同的总花费，这是因为木头在锯的过程中的长度不一。

输入格式第一行，一个整数N，表示要锯出的木头数；
第二至第N+1行，每行一个整数，表示每根木头的长度。

输出格式一个整数。表示他最少需要多少分钱，锯N-1下，锯出所有需要的木头。

输入样例 3
8
5
8

输出样例 34 题解这个数据范围，不能dp。但是显然贪心也很难找到策略。
正难则反。其实我们可以把题目反过来看：有$n$个木板，可以合并$n - 1$次，每次合并的费用为合并后的木板的和。
这样看的话，我们每次只需要合并最短的两个木板即可。

文章图片

文章图片

#include #include #include #define MAX_N (20000 + 5)using namespace std; int n; priority_queue , greater > q; long long ans; int main() { scanf("%d", &n); long long tmp; for(register int i = 1; i <= n; ++i) { scanf("%lld", &tmp); q.push(tmp); } while(--n) { tmp = q.top(); q.pop(); tmp += q.top(); q.pop(); q.push(tmp); ans += tmp; } printf("%lld", ans); return 0; }

参考程序
【【题解】木板】转载于:https://www.cnblogs.com/kcn999/p/11218458.html