# Solution to the problem of merging stones

[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.

Tags: less

Posted on Sun, 17 May 2020 08:01:51 -0700 by jswinkelman