題目
題目鏈接：P1880 [NOI1995] 石子合并
一道區間 DP 的典型題目，
區間 DP
特點
- 合并：將兩個或多個部分進行整合，當然也可以反過來，
- 特征：能將問題分解為能兩兩合并的形式，
- 求解：對整個問題設最優值，列舉合并點，將問題分解為左右兩個部分，最后合并兩個部分的最優值得到原問題的最優值，
狀態轉移
下面，我們先考慮不在環上，而在一條鏈上的情況，
令狀態 \(f(i,j)\) 表示將下標在 \([i,j]\) 區間的元素合并起來所能獲得的最大價值，則 \(f(1,n)\) 就是問題的答案，狀態轉移式為：
\[f(i,j)=\max\{f(i,k)+f(k+1,j)+cost(i,j,k)\},\quad k\in[i,j) \]\(cost(i,j,k)\) 表示將區間 \([i,k]\) 和 \([k+1,j]\) 合并為 \([i,j]\) 的代價，這里的 \(k\) 就是要列舉的合并點，
遞推求解
使用遞推法求解區間 DP 時，通常的做法是從小到大列舉區間長度，這樣能保證在求解大區間時，小區間的答案已經被求解出來了，
演算法模板如下，時間復雜度 \(O(n^3)\)，
for (int len = 2; len <= n; len++)
{
for (int i = 1; i <= n; i++)
{
int j = i + len - 1;
for (int k = i; k < j && k <= n; k++)
{
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + cost(i, j, k));
}
}
}
環上的區間 DP
現在讓我們回到原問題，怎么處理在環上的情況呢？
如果是在一個長為 \(n\) 的環上，那么弄一條長為 \(2n\) 的鏈（重復一次），DP 求解后取 \(f(1,n),f(2,n+1),\ldots,f(n-1,2n-1)\) 中的最優值即可，時間復雜度仍為 \(O(n^3)\)，
參考資料：區間 DP - OI Wiki
代碼
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = int(1e9);
const int maxn = 100 + 5;
int dp_min[maxn * 2][maxn * 2];
int dp_max[maxn * 2][maxn * 2];
int arr[maxn * 2];
int prefix_sum[maxn * 2];
//由于我們要把鏈重復一次，所以陣列要開兩倍大小
//預處理出前綴和
void calc_prefix_sum(int n)
{
prefix_sum[0] = 0;
for (int i = 1; i <= 2 * n - 1; i++)
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
}
//[x, y] 的區間和
int sum(int x, int y)
{
return prefix_sum[y] - prefix_sum[x - 1];
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int a;
scanf("%d", &a);
arr[i] = arr[n + i] = a;
}
calc_prefix_sum(n);
//遞推求解
for (int len = 2; len <= n; len++)
{
for (int i = 1; i <= 2 * n - 1; i++)
{
int j = i + len - 1;
int temp_min = INF;
int temp_max = 0;
//列舉合并點 k，計算將 [i, k] 和 [k+1, j] 合并所需的花費
for (int k = i; k < j && k <= 2 * n - 1; k++)
{
temp_min = min(temp_min, dp_min[i][k] + dp_min[k + 1][j] + sum(i, j));
temp_max = max(temp_max, dp_max[i][k] + dp_max[k + 1][j] + sum(i, j));
}
dp_min[i][j] = temp_min;
dp_max[i][j] = temp_max;
}
}
int ans_min = dp_min[1][n];
int ans_max = dp_max[1][n];
for (int i = 2; i <= n - 1; i++)
{
ans_min = min(ans_min, dp_min[i][i + n - 1]);
ans_max = max(ans_max, dp_max[i][i + n - 1]);
}
printf("%d\n%d", ans_min, ans_max);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/243795.html
標籤：其他