題目背景

上元節(jié)的廟會上，牛寶靠自己的聰明才智成功破解了花燈陣，點亮了在場所有花燈，但他沒料到的是這個游戲包含AB兩個項目，A項目就是點亮所有花燈，而B項目則是熄滅所有花燈。不過點亮的是花燈陣，熄滅的則是花燈環(huán)。
題目描述

熄滅花燈環(huán)的規(guī)則如下：

在一個環(huán)形的花燈圈中，每隔一段距離擺放著一個花燈堆，每個花燈堆都由一定數(shù)量的花燈組成，共有n個花燈堆(n<= 100)，現(xiàn)要將花燈全部熄滅，需要消耗牛寶體力值為10。不過在熄滅花燈之前，必須先將所有花燈堆聚集到一起才行。牛寶體力有限，每次只能將相鄰的兩個花燈堆聚集在一起,聚集成的新花燈堆的花燈數(shù),即為牛寶消耗的體力值。

讀入花燈堆數(shù)n及每堆的花燈數(shù)(<=20)。選擇一種最佳聚集花燈的策略,使得所有花燈堆聚集到一起后,牛寶消耗的體力值最小,輸出牛寶將花燈全部聚齊并熄滅所消耗的最少體力值。
輸入格式

第一行輸入一個整數(shù)n,代表環(huán)形花燈圈上有n個花燈堆

第二行輸入組成每個花燈堆的花燈數(shù)
輸出格式

輸出一個整數(shù)，代表牛寶將花燈全部聚齊并熄滅所消耗的最少體力值
輸入輸出樣例
輸入

4
4 4 5 9

輸出

53

說明/提示

牛寶正在愁思記錄著搬運花燈堆所要耗費的體力。。。

話說第一次寫這題的時候，還不知道區(qū)間dp這東西，我居然用循環(huán)鏈表模擬一個環(huán)，結果只能過一個數(shù)據(jù)點。(還是太年輕了)
循環(huán)鏈表模擬環(huán)
代碼如下：

#include <iostream> using namespace std; const int N = 110;struct huan {int w;int l;int r; }; huan node[N]; int ans;int main() {int n;int cnt;cin >> n;cnt = n;for (int i = 1; i <= n; i++) {int x;cin >> x;node[i].w = x;node[i].l = i + 1;node[i].r = i - 1;}node[0].l = 1;node[0].r = n;node[1].r = 0;node[n].l = 0;node[0].w = 999999;int u;while (cnt != 1) {bool flag = 0;int minv = 99999999;for (int i = node[0].l; i; i = node[i].l) {if ((node[i].w + node[node[i].l].w) < minv && node[i].l != 0) {u = i;minv = (node[i].w + node[node[i].l].w);} else if ((node[i].w + node[node[0].l].w < minv ) && node[i].l == 0) {u = i;flag = 1;minv = (node[i].w + node[node[0].l].w);}}ans += minv;if (flag) {node[u].w += node[node[0].l].w;node[0].l = node[node[0].l].l;node[node[0].l].r = 0;cnt--;} else {node[node[u].l].w += node[u].w;node[node[u].r].l = node[u].l;node[node[u].l].r = node[u].r;cnt--;}}cout << ans + 10 << endl;return 0; }

原因就是，假如有很多花燈堆，剛好這邊有2個花堆和那邊的2個花堆合在一起所需的體力值一樣且都是最小值的時候，應該合哪邊的呢？？？
模擬環(huán)的方式無法處理這種情況，當然應該是我水平太低。

然后用區(qū)間dp來寫，就可以解決這種情況。

解題思路：
寫這道題前，先看看石子合并-區(qū)間dp這道簡單一點的
這道題與石子合并-區(qū)間dp的區(qū)別是：這道題變成了環(huán)形的，處理方式是將之前的直線石子合并 ，將前n堆石子復制到n+1到2n，變成一個2n長的直線石子合并問題
，輸出的時候枚舉dp[i][n+i-1]，找最小值。
舉個例子：
可以看到，原本假如石子是3堆，為3,4,5
那么變成環(huán)形的話，我們就變成3,4,5,3,4,5
然后處理方式還是一樣，只是最后我們輸出的結果是長度為3情況(dp[i][n+i-1])中最小值。

代碼如下：

#include <iostream> using namespace std; const int N = 101; const int INF = 1 << 30; int a[N * 2]; int s[N * 2]; int dp[2 * N][2 * N]; int n;int ans() {for (int i = 1; i <= 2 * n; i++)dp[i][i] = 0;for (int len = 1; len < 2 * n; len++)for (int i = 1; i <= 2 * n - len; i++) {int j = i + len;dp[i][j] = INF;for (int k = i; k < j; k++) {dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);}}int minv = 1 << 30;for (int i = 1; n + i - 1 <= 2 * n; i++) {minv = min(dp[i][n + i - 1], minv);}return minv; }int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = n + 1; i <= 2 * n; i++)a[i] = a[i - n];s[0] = 0;for (int i = 1; i <= 2 * n; i++) {s[i] = s[i - 1] + a[i];}cout << ans()+10 << endl;return 0; }

總結

以上是生活随笔為你收集整理的上元节的灯会(灭)-区间dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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