一开始被题目读错题= =以为每次只能割一块,那么就是从大到小切
但是其实是可以分为几堆来切的
所以可以逆着来,变为合并n个木板代价最小
易证每次找最小的两堆合并代价最小
用优先队列维护堆。。偷偷懒= =
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; priority_queue<int,vector<int>,greater<int> > Q; int n,x,y; long long ans=0LL; int main(){ scanf("%d", &n); ; i<=n; i++) scanf("%d", &x),Q.push(x); ; i<n; i++){ x=Q.top(); Q.pop(); y=Q.top(); Q.pop(); ans+=(x+y); Q.push(x+y); } printf("%lld\n", ans); ; }