1、题目大意：N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。n<=100

n^3

#include
      
       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
      

2、题目大意：N堆石子摆成一个环。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。n<=1000

n^2

#include
      
       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<
       
        <
       
      

3、题目大意：N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。n<=50000

最坏n^2,大约n^1.5

#include
      
       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
       
        =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
        
         =3&&st[t-3]<=st[t-1])combine(t-2);    }    while(t>1)combine(t-1);    printf("%lld\n",ans);    return 0;}