题目

小明有 n 颗石子，按顺序摆成一排。

他准备用胶水将这些石子粘在一起。

每颗石子有自己的重量，如果将两颗石子粘在一起，将合并成一颗新的石子，重量是这两颗石子的重量之和。

为了保证石子粘贴牢固，粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比，本题不考虑物理单位，认为所需要的胶水在数值上等于两颗石子重量的乘积。

每次合并，小明只能合并位置相邻的两颗石子，并将合并出的新石子放在原来的位置。

现在，小明想用最少的胶水将所有石子粘在一起，请帮助小明计算最少需要多少胶水。

//***思路：这道题根据两个样例测试可以不完全验证：每次去两个数的最小和粘在一起即可得出结果最小。
//想到每次输出最小，就想到优先队列（本题要求最小堆，默认最大堆）。定义一个结构体存储组成和的两个数与和的值，根据和的值排序；为了原汁原味的保留和的位置信息，将组成和的两数中左边那个位置用来存放新的和
//另一个位置置0，即无效它（没必要新开visited数组）。注意寻找新和的左右数时要跳过那些无效的数（即为0的数）。


//错误总结：最开始是想用贪心的。
//因为发现只要每次去和最小的两个石头黏在一起，结果就是最小，但是没发现好多坑啊/(ㄒoㄒ)/~~
//错误1：直接将和丢到优先队列里面然后让他找最小数 发现结果比答案要大得多 奇怪。后来才发现没有将组成最小和的那两个数无效掉/(ㄒoㄒ)/~~
//错误2：开始想的是将和赋值给组成和的两个数中左边那个位置，然后把那两个位置无效掉。后来发现那个新的和也没办法用。。。（作者太苯了对不起）
//错误3：冥思苦想  打算将扩大数组范围到n*2 然后将visited也扩大  然后发现去找新的和与左右两边的数字组成新的和时 记录左右两边为遍历过的数索引有点被绕晕了
//（现在想来是当时while里面没有更新cur.l，所以就TLE超时了
//错误4：然后煮波灵光一现  想来可以不将组成最小和的那两个位置无效掉（这下连visited都省了，妙哉(*^_^*)）  保留一个位置放新的和，将另一个数设为0 因为数据大于0.。麻麻啊，顿时一个痛哭流涕茅塞顿开
//然后发现报错  感谢报错！报错是最好的老师！ 遂认真检查了代码  发现while里没更新cur.l/cur.r  高兴，遂入寝

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long LL;

struct Node {
    int l, r; // 记录两个相邻石头的索引
    LL sum;   // 两个石头的重量和
    Node(int _l, int _r, const vector<LL>& stones) : l(_l), r(_r) {
        sum = stones[l] + stones[r];
    }
};

struct CompareNode {
    bool operator()(const Node& a, const Node& b) {
        return a.sum > b.sum; // 最小堆
    }
};

int main() {
    int n;
    cin >> n;
    vector<LL> stones(n);
    for (int i = 0; i < n; ++i) {
        cin >> stones[i];
    }

    LL result = 0;
    priority_queue<Node, vector<Node>, CompareNode> pq;

    // 初始化优先队列，存储所有相邻石头的合并操作
    for (int i = 0; i < n - 1; ++i) {
        pq.push(Node(i, i + 1, stones));
    }

    while (pq.size() >= 1) {
        Node cur = pq.top();
        pq.pop();

        // 如果当前石头已经被合并，跳过
        if (stones[cur.l] == 0 || stones[cur.r] == 0) continue;

        // 合并石头，计算代价
        result += stones[cur.l] * stones[cur.r];

        // 更新新的石头的重量
        int newWeight = stones[cur.l] + stones[cur.r];

        // 将新的石头放在 cur.l 的位置，将 cur.r 的位置设置为 0
        stones[cur.l] = newWeight;
        stones[cur.r] = 0;

        // 将新的相邻石头对加入优先队列
        while (cur.l > 0 ) {
            if(stones[cur.l - 1] == 0) 
            {
                cur.l--;continue;
            }
            pq.push(Node(cur.l - 1, cur.l, stones));break;
        }
        while (cur.r < n - 1 ) {
            if(stones[cur.r + 1] == 0)
            {
                cur.r++;
                continue;
            }
            pq.push(Node(cur.l, cur.r + 1, stones));break;
        }
         /*cout<<"---------------"<<endl;
        for(int i=0;i<n*2;i++)cout<<stones[i]<<" ";
        cout<<endl;
        cout<<"result" <<result<<" n"<<n<<" size"<<pq.size()<<endl;*/
    }

    cout << result << endl;
    return 0;
}