谁能帮我解释一下这个代码喵？

lucy2012 @ 2024-08-10 17:34:32

#include<bits/stdc++.h>
using namespace std;
const int N = 50005;
int n, stone[N], ans, t = 1;

void solve(int k){
    int tmp = stone[k] + stone[k - 1];
    ans += tmp;
    for(int i = k; i < t - 1; i++)
        stone[i] = stone[i + 1];
    t--; int j = 0;
    for(j = k - 1; j > 0 && stone[j - 1] < tmp; j--)
        stone[j] = stone[j - 1];
    stone[j] = tmp;
    while(j >= 2 && stone[j] >= stone[j - 2]){
        int d = t - j; solve(j - 1);
        j = t - d;
    }
}

int main(){
    int n; cin >> n;
    for(int i = 0; i < n; i++)
        cin >> stone[i];
    for(int i = 1; i < n; i++){
        stone[t++] = stone[i];
        while(t >= 3 && stone[t - 3] <= stone[t - 1])
            solve(t - 2);
    }
    while(t > 1) solve(t - 1);
    cout << ans << endl;
    return 0;
}

by lucy2012 @ 2024-08-10 17:40:03

@lucy2012 应该不是求石子合并最优解，那模拟的过程有何规律。我未曾知晓，世间非万物皆完美，唯余遗憾，乃唯天道。

by Hanrui1206 @ 2024-08-10 17:47:33

solve(int k) 应该是合并位置 k 和 k - 1 的石头。

by Hanrui1206 @ 2024-08-10 17:49:25

过程大概是这样的：

1. 读取石头数量 n。
2. 读取每个石头的重量并存储在 \operatorname{stone} 数组中。
3. 遍历石头数组，每次添加一个新的石头并检查是否需要合并。
4. 如果需要合并，调用 \operatorname{solve} 函数。
5. 最后，如果还有石头未合并，继续合并直到只剩一个石头。
6. 输出总的合并成本 ans。

by lucy2012 @ 2024-08-10 17:53:13

@Hanrui1206 我知道了，是把石子按树来一步步合并

by lucy2012 @ 2024-08-10 17:54:39

@Hanrui1206 曾是未意 t 欲何求。

by Hanrui1206 @ 2024-08-10 17:56:21

是当前有效的石头数量吗？

by Hanrui1206 @ 2024-08-10 17:56:35

@lucy2012

by lucy2012 @ 2024-08-10 18:01:05

@Hanrui1206 有样例曰：

5
5 4 3 2 1

曾测仍为最优解，出乃 33，步骤（最优解）因为：

合并 1 2，合并 3 3（1+2=3），合并 4 5，合并 6 9 （3+3=6）（4+5=9），代价 33（1+2+3+3+4+5+6+9=33）

by lucy2012 @ 2024-08-10 18:02:17

@Hanrui1206 何能可为最优（验证码hmn4，后面你死？不要啊！）

by SwethessPotion @ 2024-08-10 19:12:23

@lucy2012 你要是不说验证码我就不会呃呃了。。。。。。。。。

石子合并之法，乃 Huffman Tree 也。

大概就是这样：

开优先队列 q，每次做这样的操作：

int front1 = q.top();
q.pop();
int front2 = q.top();
q.pop();
q.push(front1 + front2);