問題描述：

在一個圓形操場的四周擺放著n 堆石子。現要將石子有次序地合并成一堆。
規定每次只能選相鄰的2 堆石子合并成新的一堆，并將新的一堆石子數記為該次合并的得分。
試設計一個算法，計算出將n堆石子合并成一堆的最小得分和最大得分

---

分析

要求每次合并必須是相鄰的，和矩陣鏈乘的括號作用差不多。可以考慮往矩陣鏈乘最小代價的遞歸方程上靠。設dp[i,j]為第i堆到第j堆合并的最優解，則$dp[i,j]=mindp[i,k]+dp[k+1,j]+vi+...vj$

注意由于是圓形，而矩陣鏈乘是線性的，所以這個遞歸方程勢必需要修改。考慮如何表示環，一個自然的想法是利用mod函數。遞歸方程修改如下，為了方便表示修改dp[i,j]定義如下：從第i堆開始合并j堆的最優解。（否則需要填寫的項數不全在一個矩陣半角上）

dp[i,j]=min{dp[i,k]+dp[(i+k)%n,j?k]+vi+…+vj} i<=k<=j

dp[i,j]=max{dp[i,k]+dp[(i+k)%n,j?k]+vi+…+vj} i<=k<=j

---

代碼展示

#include<iostream> #include<algorithm> #include<cstring> using namespace std; int n; int dp_max[207][207]; int dp_min[207][207]; int cost[207]; int a[203]; const int MAX = 0x3f3f3f3f;int main() {while(scanf("%d", &n) != EOF){memset(dp_min, MAX, sizeof(dp_min));memset(dp_max, 0, sizeof(dp_max));for(int i = 1; i <= n; i++){scanf("%d", &a[i]);a[i + n] = a[i];dp_min[i][i] = 0;dp_min[i + n][i + n] = 0; }cost[0] = 0;for(int i = 1; i <= 2 * n; i++)//為了后面方便用前綴和cost[i] = cost[i - 1] + a[i];for(int len = 2; len <= n; len++)//走幾步 {for(int i = 1; len + i - 1 <= 2 * n; i++)//從哪開始 {int j = len + i - 1;for(int k = i; k < j; k++){dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + cost[j] - cost[i - 1]);dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + cost[j] - cost[i - 1]);}}}int ans_min = MAX;int ans_max = -1;for(int i = 1; i <= n; i++){ans_min = min(ans_min, dp_min[i][i+n-1]);ans_max = max(ans_max, dp_max[i][i+n-1]);}cout << ans_min << " " << ans_max << endl;}return 0; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的问题描述： 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。 规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 试设计一个算法，计算出将n堆石子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。