深圳找工作哪个网站好,html网站 怎么做seo,百度浏览器主页网址,辽宁鞍山网站建设公司题干#xff1a;
一位老木匠需要将一根长的木棒切成N段。每段的长度分别为L1,L2,......,LN#xff08;1 L1,L2,…,LN 1000#xff0c;且均为整数#xff09;个长度单位。我们认为切割时仅在整数点处切且没有木材损失。
木匠发现#xff0c;每一次切割花费的体…题干
一位老木匠需要将一根长的木棒切成N段。每段的长度分别为L1,L2,......,LN1 L1,L2,…,LN 1000且均为整数个长度单位。我们认为切割时仅在整数点处切且没有木材损失。
木匠发现每一次切割花费的体力与该木棒的长度成正比不妨设切割长度为1的木棒花费1单位体力。例如若N3L1 3,L2 4,L3 5则木棒原长为12木匠可以有多种切法如先将12切成39.花费12体力再将9切成45花费9体力一共花费21体力还可以先将12切成48花费12体力再将8切成35花费8体力一共花费20体力。显然后者比前者更省体力。
那么木匠至少要花费多少体力才能完成切割任务呢
Input
第1行1个整数N(2 N 50000) 第2 - N 1行每行1个整数Li(1 Li 1000)。
Output
输出最小的体力消耗。
Sample Input
3
3
4
5
Sample Output
19
解题报告 最优合并问题夏季学期实践课的时候做过一个类似的Fence的一个切栅栏好像是还是切木板来着。需要注意的问题也都在我的那篇博客上有写。
AC代码
#include bits/stdc.h
#define ll long long
using namespace std;
ll n,tmp,ans,tmpp;
priority_queuell,vectorll,greaterll pq;
int main()
{cinn;for(int i 1; in; i) scanf(%lld,tmp),pq.push(tmp); for(int i 1; in; i) {tmp pq.top();pq.pop();tmpp pq.top(); pq.pop();ans tmp tmpp;pq.push(tmp tmpp);}printf(%lld\n,ans);return 0;
}
