板子 GarsiaWachs算法

专门用来解决石子合并问题的算法。

P5569 「SDOI2008」石子合并

数据范围：\(n\le 4\times 10^4\)。

做法

• 找到最小的 i 满足 \(a_{i-1}<a_{i+1}\)
• 合并 \(a_{i-1},a_i\)
• 找到最大的 j 满足 \(j < k\) 并且 \(a_j > a_{i-1} + a_i\)
• 将 i-1,i 合并后的石子插入到 j 后面

通过 vector 模拟，直到合并为一个元素。

注意处理边界 \(a_0=a_{n+1}=\infty\)。

时间复杂度 \(O(n^2)\)，需要开 O2 才能过 qwq。

证明见 Eastern 的博客。

代码

#include <vector>
#include <cstdio>
#include <cctype>
using namespace std;

namespace RenaMoe {
template <typename TT> inline void read(TT &x) {}

const int INF = 0x3f3f3f3f;

int n, ans;
vector<int> a;

inline void main() {
    read(n);
    a.push_back(INF);
    for (int i = 1, x; i <= n; ++i)
        read(x), a.push_back(x);
    a.push_back(INF);
    int i, j, sum;
    while (n-- > 1) {
        for (i = 1; i <= n; ++i)
            if (a[i-1] < a[i+1])
                break;
        sum = a[i-1] + a[i];
        for (j = i - 1; ~j; --j)
            if (a[j] > sum)
                break;
        a.erase(a.begin() + i - 1);
        a.erase(a.begin() + i - 1);
        a.insert(a.begin() + j + 1, sum);
        ans += sum;
    }
    printf("%d\n", ans);
}
}

int main() {
    RenaMoe::main();
    return 0;
}