经典算法 石子合并问题

石子合并问题

问题描述

在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出一个算法,计算出将N堆石子合并成1堆最大得分和最小得分。

输入描述

第一行一个整数(n)1 <= n <= 100，接下来一行n个整数，表示每堆石子的个数。

输出描述

输出第一行最小得分，第二行最大得分。

输入示例

4
4 4 5 9

输出示例

43
54

输入示例

7
6 4 36 4 7 14 25

输出示例

237
430

c++代码

#include<bits/stdc++.h>using namespace std;int main() {int n, max_val = INT_MIN, min_val = INT_MAX;cin >> n;vector<int> arr(2 * n + 1);for (int i = 1; i <= n; i++) cin >> arr[i];for (int i = n + 1; i <= 2 * n; i++) arr[i] = arr[i - n];for (int i = 1; i <= 2 * n; i++) arr[i] += arr[i - 1];vector<vector<int>> dp(2 * n + 1, vector<int>(2 * n + 1, 0));for (int len = 2; len <= 2 * n; len++) {for (int i = 1; i + len - 1 <= 2 * n; i++) {for (int j = i; j < i + len - 1; j++) {dp[i][i + len - 1] = max(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1] + arr[i + len - 1] - arr[i - 1]);}}}for (int i = 1; i <= n; i++) max_val = max(max_val, dp[i][i + n - 1]);dp = vector<vector<int>>(2 * n + 1, vector<int>(2 * n + 1, INT_MAX));for (int i = 1; i <= 2 * n; i++) dp[i][i] = 0;for (int len = 2; len <= 2 * n; len++) {for (int i = 1; i + len - 1 <= 2 * n; i++) {for (int j = i; j < i + len - 1; j++) {dp[i][i + len - 1] = min(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1] + arr[i + len - 1] - arr[i - 1]);}}}for (int i = 1; i <= n; i++) min_val = min(min_val, dp[i][i + n - 1]);cout << min_val << endl << max_val;return 0;
}//by wqs

链形的石子合并

这个题目是环形的，也就是，第一个和最后一个石子可以合并，我们来考虑链形的石子合并怎么写，再推广到环形的。

由于最大得分和最小得分的思路是一样的，我们为了减少代码的冗余度，只说最大得分的算法。

链形石子合并 c++代码()

#include<bits/stdc++.h>using namespace std;int main() {int n;cin >> n;vector<int> arr(n + 1);for (int i = 1; i <= n; i++) cin >> arr[i], arr[i] += arr[i - 1];vector<vector<int>> dp(n + 1, vector<int>(n + 1));for (int len = 1; len <= n; len++) {for (int i = 1; i + len - 1 <= n; i++) {for (int j = i; j < i + len - 1; j++) {dp[i][i + len - 1] = max(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1] + arr[i + len - 1] - arr[i - 1]);}}}cout << dp[1][n];return 0;
}

我们定义dp[i][j]表示从第i堆石子到第j堆沙子的最大得分。
我们假设i~k堆沙子合并好了,k + 1 ~ j堆沙子也合并好了
我们现在要尝试合并i~k堆沙子和k + 1 ~ j堆沙子，并计算得分是多少。
实际上得分等于dp[i][k] + dp[k + 1][j] + (i ~ j的元素的和)
dp[i][k]是i~k堆沙子累计的得分。i ~ k合并后的新沙子的值为 (i ~ k的和)
dp[k + 1][j]是k + 1 ~ j堆沙子的得分。k + 1 ~ j合并后的新沙子的值为 (k + 1 ~ j的和)
我们还要把两堆沙子合并。新沙子合并后得分为(i ~ k的和) + (k + 1 ~ j的和) = (i ~ j的元素的和)。
所以最大得分等于dp[i][k] + dp[k + 1][j] + (i ~ j的元素的和)我们要保证合并第第i堆石子到第j堆沙子前dp[i][k]和 dp[k + 1][j]的值已经知道了
也就是要先算长度短的区间状态，再算长度长的区间状态
for (int len = 1; len <= n; len++) {//第一个for循环枚举区间长度，先算长度小的区间for (int i = 1; i + len - 1 <= n; i++) {//第二个for循环枚举左端点，由左端点和区间长度算出右端点为i + len - 1for (int j = i; j < i + len - 1; j++) {//第三个for循环枚举k,用前缀和数组快速求区间和dp[i][i + len - 1] = max(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1] + arr[i + len - 1] - arr[i - 1]);}}
}

环形的石子合并

由于最大得分和最小得分的思路是一样的，我们为了减少代码的冗余度，只说最大得分的算法。

c++代码

#include<bits/stdc++.h>using namespace std;int main() {int n, max_val = INT_MIN;cin >> n;vector<int> arr(2 * n + 1);for (int i = 1; i <= n; i++) cin >> arr[i];for (int i = n + 1; i <= 2 * n; i++) arr[i] = arr[i - n];for (int i = 1; i <= 2 * n; i++) arr[i] += arr[i - 1];vector<vector<int>> dp(2 * n + 1, vector<int>(2 * n + 1, 0));for (int len = 2; len <= 2 * n; len++) {for (int i = 1; i + len - 1 <= 2 * n; i++) {for (int j = i; j < i + len - 1; j++) {dp[i][i + len - 1] = max(dp[i][i + len - 1], dp[i][j] + dp[j + 1][i + len - 1] + arr[i + len - 1] - arr[i - 1]);}}}for (int i = 1; i <= n; i++) max_val = max(max_val, dp[i][i + n - 1]);cout << max_val;return 0;
}

环形石子合并我们要采用化圈成线的思路。

具体来说，看样例

4

4 4 5 9

我们把数组拷贝一次变成

4 4 5 9 4 4 5 9

考虑4 4 5 9链形合并最大值

考虑4 5 9 4链形合并最大值

考虑5 9 4 4链形合并最大是

考虑9 4 4 5链形合并最大值

这四个最大值里面选择一个最大的就是环形最大值。

环形石子合并算法正确性证明

之所以这样做是对的，是因为n次的链形合并穷尽了环形合并的所有可能。

例如4 4 5 9，4和9环形合并变成13 4 5对应9 4 4 5，9和4链形合并13 4 5。