P5569 [SDOI2008] 石子合并

P5569 [SDOI2008] 石子合并

大意

求最小值的石子合并，\(n \le 40000\)。

思路

利用 GarsiaWachs 算法。

在序列中找到第一个满足 \(a_{i-1} \le a_{i+1}\) 的三元组 \((a_{i-1}, a_i, a_{i+1})\)。

合并 \(a_{i-1}\) 和 \(a_i\)，得分增加 \(W = a_{i-1} + a_i\)。

从当前位置向左寻找第一个大于 \(W\) 的位置，将 \(W\) 插入到其后面。

重复上述过程，直到只剩下一堆石子。

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;#define int long long
int n;
int ans = 0;
vector<int> a;void merge(int k){int tmp = a[k - 1] + a[k];ans += tmp;a.erase(a.begin() + k - 1);a.erase(a.begin() + k - 1);int pos = -1;for(int i = k - 2;i >= 0;i --){if(a[i] >= tmp){pos = i;break;}}a.insert(a.begin() + pos + 1, tmp);
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin >> n;for(int i = 1;i <= n;i ++){int val; cin >> val;a.push_back(val);}while(a.size() > 1){int k = a.size() - 1;for(int i = 1;i < (int)a.size() - 1;i ++){if(a[i - 1] <= a[i + 1]){k = i;break;}}merge(k);}cout << ans << '\n';return 0;
}