前言:
除了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;
}
撒花完结!!!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)