# OJ stone merger

### The problem of stone merging

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Around a circular playground are n heaps of stones. 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. An algorithm is designed to calculate the minimum score and the maximum score of the n-pile stones.
For a given n-pile, the minimum score and the maximum score are calculated and combined into a pile.

Input

The first row of the input data is a positive integer n, 1 ≤ n ≤ 100, indicating that there are n heaps of stones. The second line has n numbers, which represent the number of stones in each pile.

Output

The output data has two lines, the number in line 1 is the minimum score, and the number in line 2 is the maximum score.

Sample Input

```4
4 4 5 9```

Sample Output

```43
54```
```#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

#define MAXN 100

int sum[MAXN];

int mins[MAXN][MAXN], maxs[MAXN][MAXN];

int INT_MAX=999999999;

int n, stone[MAXN];

int sums(int i, int j)
{

if(i + j >= n)
{

return sums(i, n - i - 1) + sums(0, (i + j) % n);

}
else
{

return sum[i + j] - (i > 0 ? sum[i - 1] : 0);

}

}

void getBest(int& minnum, int& maxnum)
{

//Initialization, no merge, cost 0

for(int i = 0; i < n; ++i)
{

mins[i][0] = maxs[i][0] = 0;

}

for(int j = 1; j < n; ++j)
{

for(int i = 0; i < n; ++i)
{

mins[i][j] = INT_MAX;

maxs[i][j] = 0;

for(int k = 0; k < j; ++k)
{

mins[i][j] = min(mins[i][k] + mins[(i + k + 1)%n][j - k - 1] + sums(i, j), mins[i][j]);

maxs[i][j] = max(maxs[i][k] + maxs[(i + k + 1)%n][j - k - 1] + sums(i, j), maxs[i][j]);

}

}

}

minnum = mins[0][n - 1];

maxnum = maxs[0][n - 1];

for(int i = 0; i < n; ++i)
{

minnum = min(minnum, mins[i][n - 1]);

maxnum = max(maxnum, maxs[i][n - 1]);

}

}

int main()
{

scanf("%d", &n);

for(int i = 0; i < n; ++i)

scanf("%d", &stone[i]);

sum[0] = stone[0];

for(int i = 1; i < n; ++i)
{

sum[i] = sum[i - 1] + stone[i];

}

int minnum, maxnum;

getBest(minnum, maxnum);

printf("%d\n%d\n", minnum, maxnum);

return 0;

}
```

Added by echoofavalon on Mon, 25 Nov 2019 21:50:43 +0200