在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。用c++实现该问题,含算法思路及代码注释
时间: 2023-09-14 22:09:22 浏览: 39
算法思路:
我们可以使用动态规划来解决这个问题。设f[i][j]表示将第i堆石子到第j堆石子合并成一堆的最小得分,g[i][j]表示将第i堆石子到第j堆石子合并成一堆的最大得分。则有以下状态转移方程:
f[i][j] = min(f[i][k] + f[k+1][j] + sum[i][j]) (i ≤ k < j)
g[i][j] = max(g[i][k] + g[k+1][j] + sum[i][j]) (i ≤ k < j)
其中sum[i][j]表示第i堆石子到第j堆石子的总数。初始状态为f[i][i] = g[i][i] = 0。最终答案为f[1][n]和g[1][n]。
代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 310;
int n;
int w[N];
int f[N][N], g[N][N], sum[N][N];
int main()
{
cin >> n;
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= n; i++)
{
cin >> w[i];
sum[i][i] = w[i];
f[i][i] = 0, g[i][i] = 0;
}
for (int len = 2; len <= n; len++)
{
for (int i = 1; i + len - 1 <= n; i++)
{
int j = i + len - 1;
sum[i][j] = sum[i][j - 1] + w[j];
for (int k = i; k < j; k++)
{
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + sum[i][j]);
g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + sum[i][j]);
}
}
}
cout << f[1][n] << ' ' << g[1][n] << endl;
return 0;
}
```
代码注释:
第2行:定义数组大小
第4 ~ 5行:定义变量n和数组w
第6 ~ 9行:初始化f[i][i]、g[i][i]和sum[i][i]
第10行:读入每堆石子的个数
第11行:计算sum[i][i]
第12 ~ 18行:使用动态规划求解最小得分和最大得分
第19行:输出f[1][n]和g[1][n]