石子合并——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
#define pb push_back
#define int long long//十年 oi 一场空 , 不开 long long 见祖宗! 
using namespace std;

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

//快读快写不解释 
template
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
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;ires)
        {
        	//找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;
}

撒花完结！！！