[Title Description]
N piles of stones are placed in rows on a playground. Now we will combine the stones into a pile in order. It is stipulated that only two adjacent piles of stones can be selected to merge into a new pile at a time, and the number of new piles of stones shall be recorded as the score of this combination.

Calculate the minimum score of combining n piles of stones into a pile.

[input]
The first line is a positive integer N (2 ≤ n ≤ 100);

The following N lines, one positive integer for each line, less than 10000, respectively represent the number of stones in pile i (1 ≤ i ≤ N).

[output]
A positive integer is the minimum score.

[input example]
7
13
7
8
16
21
4
18
[sample output]
239

The classic chain DP and the merge fruit are totally two types, because only two adjacent heaps can be selected for merging.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int f[101][101],s[101],n,x;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        s[i]=s[i-1]+x;
    }
    memset(f,127/3,sizeof(f));
    for(int i=1;i<=n;i++)  f[i][i]=0;
    for(int i=n-1;i>=1;i--)
      for(int j=1+i;j<=n;j++)
        for(int k=i;k<=j-1;k++)
          f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
    printf("%d",f[1][n]);
    return 0;
}

The above is a chain case. What if the stones are placed in a ring?

[Title Description]

N piles of stones are placed around a circular playground. Now, the stones should be combined into a pile orderly. It is stipulated that only two adjacent piles can be combined into a new pile at a time, and the number of stones in a new pile should be recorded as the score of this combination.

An algorithm is designed to calculate the minimum score and the maximum score of N pile stones

The classic broken rings are chained, and the array becomes 2*n length.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=1005;

long long n,minn=0x7ffff,maxx,f1[maxn][maxn],f2[maxn][maxn],a[maxn],s[maxn][maxn];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[n+i]=a[i];//To become a chain
    }
    for(int i=1;i<=2*n;i++){
        for(int j=i;j<=i+n-1;j++)
          s[i][j]=s[i][j-1]+a[j];
    }
    memset(f1,127/3,sizeof(f1));
    for(int i=1;i<=2*n;i++) f1[i][i]=0;
    for(int t=2;t<=n;t++){
        for(int i=1;i<=2*n-t+1;i++){
            int j=i+t-1;
            for(int k=i;k<=j-1;k++)
            f1[i][j]=min(f1[i][j],f1[i][k]+f1[k+1][j]+s[i][j]),
            f2[i][j]=max(f2[i][j],f2[i][k]+f2[k+1][j]+s[i][j]);
        }

    }
    for(int i=1;i<=n;i++){
        minn=min(minn,f1[i][i+n-1]);
        maxx=max(maxx,f2[i][i+n-1]);
    }
    cout<<minn<<endl<<maxx;
    return 0;
}

Yesterday, I went to the mall. I feel deeply and keep on working hard.