It can be proved that all the costs of different ways to merge n piles of stones are equal.So we just need to simply do the procession in O(N)
#include<bits/stdc++.h>
using namespace std;
int n;
int x;
long long res=0;
int main(){
cin>>n;
long long pre;
cin>>pre;
for(int i=2;i<=n;++i){
int now;
cin>>now;
res+=pre*now;
pre+=now;
}
cout<<res;
return 0;
}
为什么是 equal的
因为每个石子都会被其他石子乘一次重量