bzoj 3229: [Sdoi2008]石子合并 （GarsiaWachs算法）

题目描述

传送门

题解

石子合并应该算是比较经典的问题了。 f(i,j) 表示区间 [i,j] 合并的最小代价， f(i,j)=min{f(i,k)+f(k+1,j)+sum(i,j)} 最裸的DP是 O(n3) ,利用四边形不等式优化可以做到 O(n2) ,但是对于这道题的数据范围还是不够，我们需要更优越的算法——GarsiaWachs算法 这个算法是 O(n2) ，但是是不严格的，那么在大多数情况下时间复杂度是接近 O(nlogn)

代码

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #define N 500003 #define LL long long using namespace std; int a[N],t,n; LL ans; void combine(int k) { int tmp=a[k-1]+a[k]; ans+=tmp; for (int i=k;i<t-1;i++) a[i]=a[i+1]; t--; int j=0; for (j=k-1;j>0&&a[j-1]<tmp;j--) a[j]=a[j-1]; a[j]=tmp; while (j>=2&&a[j]>=a[j-2]) { int d=t-j; combine(j-1); j=t-d; } } int main() { freopen("a.in","r",stdin); scanf("%d",&n); for (int i=0;i<n;i++) scanf("%d",&a[i]); t=1; for (int i=1;i<n;i++) { a[t++]=a[i]; while (t>=3&&a[t-3]<=a[t-1]) combine(t-2); } while (t>1) combine(t-1); printf("%lld\n",ans); }

决策单调性Ｏ(n^2)

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 1003 using namespace std; int f[N][N],val[N],n,sum[N],s[N][N]; int main() { freopen("a.in","r",stdin); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&val[i]); for (int i=1;i<=n;i++) sum[i]=sum[i-1]+val[i]; memset(f,127/3,sizeof(f)); for (int i=1;i<=n;i++) f[i][i]=0,s[i][i]=i; for (int l=2;l<=n;l++) { s[n-l+1][n]=n; for (int i=n-l+1;i>=1;i--) { int j=i+l-1; for (int k=s[i][j-1];k<=s[i+1][j];k++) { int tmp=f[i][k]+f[k+1][j]+sum[j]-sum[i-1]; if (tmp<f[i][j]) f[i][j]=tmp,s[i][j]=k; } } } printf("%d\n",f[1][n]); }