石子合并——GarsiaWachs算法

前言：

        除了O(N^2)的动态规划做法外，还有 O( nlogn) 的非动态规划做法。

                                                                                                                       ——《算法进阶指南》

这就是今天的主角：GarsiaWachs算法。

算法介绍：

        GarsiaWachs，一个专为石子合并而生的算法。

        它的大致流程如下：

        设一个序列是A[0..n-1]，每次寻找最小的一个满足A[k-1]<=A[k+1]的k，

        那么我们就把A[k]与A[k-1]合并，之后找最大的一个满足A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。

        有定理保证，如此操作后问题的答案不会改变，且时间复杂度为 nlogn。
      

定理证明详见《The Art of Computer Programming》第3卷6.2.2节。

所以呢？？？

上代码！！！

#include<bits/stdc++.h>
#define pb push_back
#define int long long//十年 oi 一场空 , 不开 long long 见祖宗! 
using namespace std;

int n,ans;
vector<int> a;//要  vector 或 快读快些  教程的,我觉得有必要给我打零花钱。 

//快读快写不解释 
template<typename type>
inline void read(type &x){x=0;bool flag(0);char ch=getchar();while(!isdigit(ch)) flag=ch=='-',ch=getchar();while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();flag?x=-x:0;}
template<typename type>
inline void write(type x,int flag){x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);do Stack[++top]=x%10,x/=10; while(x);while(top) putchar(Stack[top--]|48);if(flag==0);else if(flag==1){putchar(' ');}else {puts("");}}

int check(void);

//养成好习惯 ,从这里阅读！ 
signed main()
{
    read(n);
    
    for(int i=1;i<=n;++i)
    {
    	int x;
    	read(x);
        a.pb(x);
    }
	
    for(int i=0;i<n-1;++i)
    {
        ans+=check();
    }
    
	write(ans,2);
	
    return 0;
}

//! ! ! 敲重点 ! ! ! 
int check()
{
    int k=a.size()-2;//如果我们在A[0]到A[n-3]找不到A[k]<=A[k+2]，那么k的值应该为n-2。 
    for(int i=0;i<a.size()-2;++i)
    {
        if(a[i]<=a[i+2])
        {
        	//寻找最小的一个满足A[k-1]<=A[k+1]的 k。 
        	//只找第一个 。 
            k=i;
            break;
        }
    }
    //res是合并代价 。 
    int res=a[k]+a[k+1]; 

	//删除。 
	//这里有人要问了:不是把A[k]与A[k-1]合并吗?怎么连删两次A[k-1]?
	//这是因为第一次删除后,A[k]就到变成了A[k-1]。 
    a.erase(a.begin()+k);
    a.erase(a.begin()+k);

    int _k=-1; 
    for(int i=k-1;i>=0;--i) 
    {
        if(a[i]>res)
        {
        	//找A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。 
            _k=i;
            break; 
        }
    }
    
    //插入 。 
    a.insert(a.begin()+_k+1,res);
    
    //返回代价 。 
    return res;
}
           

撒花完结！！！