引言

關于這個區間 $DP$ ，其實是有套路和模板的，題型的話也是變化不多，感覺就那幾種，只不過有些題會用到高精度或者是要記錄方案，所以整體來說還是比較容易的了，然后這種題型還是多見的為好，目前也只是會做這幾道題。其實關于藍橋杯只要你暴力都能打滿，那么國三是穩了的，如果能做對大概兩道題，那么就能拿國二，所以說搞這個 $DP$ 也只是看能不能碰見做過類似的題目，現場解題我是不敢想了，太難的壓根做不出來，但也不能完全不學，不是特別難的還是要學，萬一出了那就是自己賺了，所以繼續加油吧，另外感覺身體累了，也是要合理的休息的！

---

區間合并模板

memset(f, 0x3f, sizeof f);  //先全部初始化為非法狀態 
for(int len = 1; len <= n; ++len)  // 確定r
{for(int l = 1; l + len - 1 <= n; ++l)  //確定l{int r = l + len - 1;if(l == r) f[l][r] = 0;  // 計算f[l][r]else  // 計算f[l][r]{for(int k = l; k < r; ++k) f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + ...);}}
}

---

一、石子合并

標簽：動態規劃、區間DP

思路：這個區間 $DP$ 其實用之前的分析法也是可以的，一般狀態定義都是看經驗，定義一個狀態 $f[i][j]$ 代表合并 $i～j$ 區間內的石子所要花費的最小的代價，狀態計算也是跟那個 $Floyd$ 算法差不多，就是把這一個區間按照倒數第二步劃分，也就是把 $f[i][j]$ 按照分界點劃分為 $f[i][k],f[k+1][j]$ ，然后再進行取最小值。兩堆石子合并所花費的最小的代價，就是合并成兩堆石子各自的最小代價加上這兩堆石子總的代價，前面的也就是 $f[i][k],f[k+1][j]$ 了，后面的可以直接拿前綴和來做即可。那么狀態轉移方程就為 $f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]?s[l?1])$ ，然后初始的狀態 $f[i][i]$ 的值為 $0$ ，然后其余的都是非法的，并且該題求的是最小值，所以初始化為正無窮即可。剩余的就按照模板即可。

題目描述：

設有 N 堆石子排成一排，其編號為 1,2,3,…,N。每堆石子有一定的質量，可以用一個整數來描述，現在要將這 N 堆石子合并成為一堆。每次只能合并相鄰的兩堆，合并的代價為這兩堆石子的質量之和，合并后與這兩堆石子相鄰的石子將和新堆相鄰，合并時由于選
擇的順序不同，合并的總代價也不相同。例如有 4 堆石子分別為 1 3 5 2， 我們可以先合并 1、2 堆，代價為 4，得到 4 5 2， 又合并 1、2 堆，代價為 9，得到 9 2 ，再合
并得到 11，總代價為 4+9+11=24；如果第二步是先合并 2、3 堆，則代價為 7，得到 4 7，最后一次合并代價為 11，總代價為 4+7+11=22。問題是：找出一種合理的方法，使總的代價最小，輸出最小代價。輸入格式
第一行一個數 N 表示石子的堆數 N。第二行 N 個數，表示每堆石子的質量(均不超過 1000)。輸出格式
輸出一個整數，表示最小代價。數據范圍
1≤N≤300
輸入樣例：
4
1 3 5 2
輸出樣例：
22

示例代碼：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 310, M = N, INF = 0x3f3f3f3f;int n, m;
int s[N], f[N][N];int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i) cin >> s[i], s[i] += s[i-1];memset(f, 0x3f, sizeof f);for(int len = 1; len <= n; ++len){for(int l = 1; l + len - 1 <= n; ++l){int r = l + len - 1;if(l == r) f[l][r] = 0;else{for(int k = l; k < r; ++k) f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l-1]);}}}cout << f[1][n] << endl;return 0;
}

---

二、環形石子合并

標簽：DP、區間DP、環形區間DP

思路：這道題跟上一道題唯一的不同就是該題的石子是環形的，不是鏈形的，解決的辦法都是在該鏈的基礎上在追加一條鏈，然后在此基礎上做區間 $DP$ ，最后再枚舉每 $n$ 堆石子找最值。為什么這樣做是正確的呢，如下圖所示，如果我們把圓圈看作石子，連邊看作是石子之間的合并，那么必然會連 $n?1$ 條邊，那么肯定會如下圖所示會有一個缺口，我們把其展開就是一條長度為 $n$ 的鏈了，那么我們直接枚舉這個缺口，也就是在 $2n$ 的長度下做區間為 $n$ 的區間合并，最后再枚舉所有長度為 $n$ 的區間的結果即可。其余的初始化等細節，詳情見代碼。

題目描述：

將 n 堆石子繞圓形操場排放，現要將石子有序地合并成一堆。規定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數記做該次合并的得分。請編寫一個程序，讀入堆數 n 及每堆的石子數，并進行如下計算：選擇一種合并石子的方案，使得做 n?1 次合并得分總和最大。選擇一種合并石子的方案，使得做 n?1 次合并得分總和最小。輸入格式
第一行包含整數 n，表示共有 n 堆石子。第二行包含 n 個整數，分別表示每堆石子的數量。輸出格式
輸出共兩行：第一行為合并得分總和最小值，第二行為合并得分總和最大值。數據范圍
1≤n≤200
輸入樣例：
4
4 5 9 4
輸出樣例：
43
54

示例代碼：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 410, M = N, INF = 0x3f3f3f3f;int n, m;
int w[N], s[N];
int f[N][N], g[N][N];int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i){cin >> w[i];w[i+n] = w[i];}for(int i = 1; i <= n * 2; ++i) s[i] = w[i] + s[i-1];memset(f, 0x3f, sizeof f);memset(g, -0x3f, sizeof g);for(int len = 1; len <= n; ++len){for(int l = 1; l + len - 1 <= n * 2; ++l){int r = l + len - 1;if(l == r) f[l][r] = g[l][r] = 0;else{for(int k = l; k < r; ++k){f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l-1]);g[l][r] = max(g[l][r], g[l][k] + g[k+1][r] + s[r] - s[l-1]);}}}}int r1 = INF, r2 = -INF;for(int i = 1; i <= n; ++i){r1 = min(r1, f[i][i+n-1]);r2 = max(r2, g[i][i+n-1]);}cout << r1 << endl << r2 << endl;return 0;
}

---

三、能量項鏈

標簽：DP、區間DP、破環成鏈

思路：這道題其實跟上一道題是差不多的， 區別就是 $len$ 最小從 $2$ 變成 $3$ 了，并且總的長度變為了 $n+1$ ，由于題目特性，兩顆珠子根據首尾也能合并成一個珠子。所以最終的結果就是 $f[i][i+n]$ 里選一個，因為 $len$ 最小是 $3$ ，所以 $l<k<r$ ，狀態轉移方程為 ${\sum }_{k=l+1}^{k=r?1}f[l][r]=max(f[l][r],f[l][k]+f[k][r]+w[l]?w[k]?w[r])$ 。其余的就是模板，細節見代碼。

題目描述：

在 Mars 星球上，每個 Mars 人都隨身佩帶著一串能量項鏈，在項鏈上有 N 顆能量珠。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數。并且，對于相鄰的兩顆珠子，前一顆珠子的尾標記一定等于后一顆珠子的頭標記。因為只有這樣，通過吸盤（吸盤是 Mars 人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被
吸盤吸收的能量。如果前一顆能量珠的頭標記為 m，尾標記為 r，后一顆能量珠的頭標記為 r，尾標記為 n，則聚合后釋放的能量為 m×r×n
（Mars 單位），
新產生的珠子的頭標記為 m，尾標記為 n。需要時，Mars 人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設計一個聚合順序，使一串項鏈釋放出的總能量最大。例如：設 N=4，4 顆珠子的頭標記與尾標記依次為 (2，3)(3，5)(5，10)(10，2)。我們用記號 ⊕ 表示兩顆珠子的聚合操作，(j⊕k) 表示第 j，k 兩顆珠子聚合后所釋放的能量。則第 4、1 兩顆珠子聚合后釋放的能量為：(4⊕1)=10×2×3=60。這一串項鏈可以得到最優值的一個聚合順序所釋放的總能量為 ((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710。輸入格式
輸入的第一行是一個正整數 N，表示項鏈上珠子的個數。第二行是 N 個用空格隔開的正整數，所有的數均不超過 1000，第 i 個數為第 i 顆珠子的頭標記，當 i<N 時，第 i 顆珠子的尾標記
應該等于第 i+1 顆珠子的頭標記，第 N 顆珠子的尾標記應該等于第 1 顆珠子的頭標記。至于珠子的順序，你可以這樣確定：將項鏈放到桌面上，不要出現交叉，隨意指定第一顆珠子，然后按順時針方向確定其他珠子的順序。輸出格式
輸出只有一行，是一個正整數 E，為一個最優聚合順序所釋放的總能量。數據范圍
4≤N≤100,1≤E≤2.1×109
輸入樣例：
4
2 3 5 10
輸出樣例：
710

示例代碼：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 210, M = N, INF = 0x3f3f3f3f;int n, m;
int w[N], f[N][N]; int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i) cin >> w[i], w[i+n] = w[i];memset(f, -0x3f, sizeof f);for(int len = 1; len <= n + 1; ++len){for(int l = 1; l + len - 1 <= n * 2; ++l){int r = l + len - 1;if(r - l + 1 < 3) f[l][r] = 0;else{for(int k = l + 1; k < r; ++k){f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);}}}}int res = 0;for(int i = 1; i <= n; ++i){res = max(res, f[i][i+n]);}cout << res << endl;return 0;
}