题解 P5569 【[SDOI2008]石子合并】
jyz666
2020-08-04 21:21:26
# 题解 P5569 【[SDOI2008]石子合并】
[传送门](https://www.luogu.com.cn/problem/P5569)
这题一开始一看，还以为是双倍经验。。
写一个普通dp。
AC：3 RE：7
仔细一看是一个加强版，N<=40000
啊这。。。
费（kan）尽（le）心（ti）思（jie），才知道原来这道题要用GarsiaWachs算法。
这个算法简述来说就是：加入有$a,b,c$三个石子堆
先合并左边两个的代价是$2a+2b+c$，而先合并右边两个的代价是$a+2b+2c$，所以只用看$a$和$c$，$a<c$
于是先合并$a<c$的吧，完了之后如果还有剩就从右边开始合并$bc$
合并$ab$的时候，合并之后插入从左边数第一个大于他的数的后面开始，究竟为什么这么做我也不怎么理解。。。
但是如果这道题就这样按照所说的话会$TLE$
，因为插入删除都是$O(n)$的，所以只好想个办法让这个$n$变得比较小
新开了一个数组，一个一个加石头进去，满足$a b$的合并条件就合并，这样会保持$n$比较小
### 上代码》》
```cpp
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define maxn 50010
#define inf 0x3f3f3f3f
const int mod=100003;
void read(int &x){
int f=1;x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
int n,w; long long ans=0;
vector<int> l;
int solu(){
int k=l.size()-2,q=-1;
for(int i=0;i<l.size()-2;++i) if (l[i]<=l[i+2]) {k=i;break;}
int t=l[k]+l[k+1];
l.erase(l.begin()+k);l.erase(l.begin()+k);
for(int i=k-1;i>=0;--i) if (l[i]>t) {q=i; break;}
l.insert(l.begin()+q+1,t);
return t;
}
int main(){
read(n);
for(int i=1;i<=n;++i) read(w),l.push_back(w);
for(int i=0;i<n-1;i++) ans+=solu();
printf("%lld",ans);
return 0;
}
```
### _勝負は時の運、と言うでしょ？_