GarsiaWachs算法（P5569石子合并）

licn · 2023-08-21 22:40:13 · 题解

介绍一下一个专门解决石子合并问题的算法，GarsiaWachs 算法。（本算法局限性较强可以了解一下）

做法：

我们把合并过程看成一颗树，它一定是一个二叉树。但是合并顺序影响结果的是合并顺序如何去找出正确的合并顺序？

1.寻找本次需要合并的点：从左往右找到第一个 a_{i-1}<a_{i+1} 我们将 a_{i-1} 和 a_{i} 合并。

2.合并之后放置的位置：从 i-1 开始向左找到第一个 a_{j}>a_i+a_{i-1} 将 a_i+a_{i-1} 插入到 j 前面。并且将原来位置上的删掉。

可使用动态数组实现，将 a_0 和 a_{n+1} 赋为 \infty 方便操作。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e4+10,M=1e16;
int n,ans,x;
vector<int>v;
signed main(){
    scanf("%lld",&n);
    v.push_back(M);
    for(int i=1;i<=n;i++)scanf("%lld",&x),v.push_back(x);
    v.push_back(M);
    n++;
    while(n--&&n>1)
    {
        int i;
        for(i=1;i<=n;i++)
            if(v[i-1]<v[i+1])break;
        int ret=v[i-1]+v[i];
        ans+=ret;
        int k;
        for(k=i-1;k>=0;k--)
            if(v[k]>ret)break;
        v.erase(v.begin()+i-1);
        v.erase(v.begin()+i-1);//删除原来位置
        v.insert(v.begin()+k+1,ret);//将合并出来的值插入
    }
    printf("%lld",ans);
    return 0;
}