1、题目大意：N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。n<=100
n^3
#include<bits/stdc++.h> using namespace std; int n; int a[1010]; int f[1010][1010]; int main(){ cin>>n; for(int i=1;i<=n;++i)cin>>a[i]; for(int i=1;i<=n;++i)a[i]+=a[i-1]; for(int len=2;len<=n;++len) for(int i=1;i<=n-len+1;++i){ int j=i+len-1; f[i][j]=1<<30; for(int k=i;k<j;++k) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]); } cout<<f[1][n]; return 0; }
2、题目大意：N堆石子摆成一个环。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。n<=1000
n^2
#include<bits/stdc++.h> using namespace std; int n; int a[2010]; int s[2010][2010]; int w[2010][2010]; int f[2010][2010]; int main(){ cin>>n; for(int i=1;i<=n;++i)cin>>a[i]; for(int i=1;i<=n;++i)a[i+n]=a[i]; for(int i=1;i<=n*2;++i){ s[i][i]=i; w[i][i]=a[i]; } for(int i=1;i<=n*2;++i) for(int j=i;j<=n*2;++j) w[i][j]=w[i][j-1]+a[j]; for(int len=2;len<=n;++len) for(int i=1;i<=n*2-len+1;++i){ int j=i+len-1; f[i][j]=1<<30; for(int k=s[i][j-1];k<=s[i+1][j];++k){ int tmp=f[i][k]+f[k+1][j]+w[i][j]; if(f[i][j]>tmp){ f[i][j]=tmp; s[i][j]=k; } } } int ans=1<<30; for(int i=1;i<=n;++i) ans=min(ans,f[i][i+n-1]); cout<<ans<<endl; }
3、题目大意：N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。n<=50000
最坏n^2,大约n^1.5
#include<bits/stdc++.h> using namespace std; const int N=50005; int st[N]; int n,t; long long ans; void combine(int k){ long long tmp=st[k]+st[k-1]; ans+=tmp; for(int i=k;i<t-1;++i) st[i]=st[i+1]; t--; int j=0; for(j=k-1;j&&st[j-1]<tmp;--j) st[j]=st[j-1]; st[j]=tmp; while(j>=2&&st[j]>=st[j-2]){ int d=t-j; combine(j-1); j=t-d; } } int main(){ scanf("%d",&n); for(int i=0;i<n;++i) scanf("%d",st+i); t=1; for(int i=1;i<n;++i){ st[t++]=st[i]; while(t>=3&&st[t-3]<=st[t-1])combine(t-2); } while(t>1)combine(t-1); printf("%lld\n",ans); return 0; }
原文：http://www.cnblogs.com/117208-/p/5369857.html
