题解 P5569 【[SDOI2008]石子合并】

· · 题解

题解 P5569 【[SDOI2008]石子合并】

传送门

这题一开始一看，还以为是双倍经验。。

写一个普通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比较小

上代码》》

#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;
}

勝負は時の運、と言うでしょ？