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;
}
//Number of additional merges required
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;
}