Algorithm2.2 区间dp
[TOC]
区间dp
区间基本提取
https://www.luogu.com.cn/problem/P2426
题目大意：删除一段数组的数，代价为这个区间的左右端点值的差的绝对值*长度，求全部删去的最大代价。
区间DP的水题，维护一个dp二维数组，然后三层遍历左右端点+中间割点，利用状态转移方程dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])即可。
注意：要上来初始化一下，初始化的值就是运算法则算出来的，而dp所做的就是排列组合来搜索组合。
#include <iostream>
using namespace std;
const int maxn = 105;
int n, a[maxn], dp[maxn][maxn]; // dp[i][j] 表示区间[i, j]所获得的最大价值
// dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]);
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a+i);
for (int i = 1; i <= n; ++i)
for (int l = 0; l+i <= n; ++l)
if (l == 0) dp[i][i+l] = a[i];
else dp[i][i+l] = abs(a[i]-a[i+l])*(l+1);
for (int i = 1; i <= n; ++i)
for (int j = i+1; j <= n; ++j)
for (int k = i; k <= j; ++k)
dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]);
printf("%d\n", dp[1][n]);
return 0;
}
石子合并（线型）
石子合并（环形）
https://www.luogu.com.cn/problem/P1880
题目大意：环形的一圈石子，合并相邻的两个，得到最大的和最小的合并代价。
1、不可以用贪心，因为贪心出来的话，不能确定选取的那最小的两个是相邻的，因为题目要求只能合并最小的两个
2、把环形拆解成链状，也就是转换成了第一个问题，线性的问题。 => 通过延长到2倍的长度。
for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);a[i+n] = a[i];}
思路类似于原来的并查集的对立集，也是将数组长度延长到了两倍
3、遍历次序：通过先遍历长度，然后再遍历左索引i，从而得到右索引j，就得到一个区间(i, i+len-1)，然后再在区间中遍历k，也就是分割点即可。dp_max[i][j] = max(dp_max[i][j], dp_max[i][k]+dp_max[k+1][j]+cost(i, j));
4、代价计算：通过前缀和来维护，或者直接用区间来算出来。sum[i][j]表示合并区间的代价
#include <iostream>
#include <climits>
using namespace std;
#define maxn 210
#define INF INT_MAX
int n, a[maxn], sum[maxn][maxn], dp_min[maxn][maxn], dp_max[maxn][maxn], ans_min = INF, ans_max;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);a[i+n] = a[i];}
for (int i = 1; i <= 2*n; i++)
for (int j = 1; j <= 2*n; j++)
for (int k = i; k <= j; k++)
sum[i][j] += a[k];
for (int i = 1; i <= n; ++i) dp_min[i][i] = dp_max[i][i] = 0;
for (int len = 1; len < n; len++)
for (int i = 1, j = i+len; i <= 2*n - 1 && j < 2*n; i++, j = i + len) {
dp_min[i][j] = INF;
for (int k = i; k < j; k++) {
dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + sum[i][j]);
dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + sum[i][j]);
}
}
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]);}
printf("%d\n%d\n", ans_min, ans_max);
return 0;
}
能量项链（环形）
https://www.luogu.com.cn/problem/P1063
题意和石子归并类似，只不过在计算cost成本的时候略有区别
1、区分和石子归并不同的遍历方式：石子归并是先枚举长度，然后再枚举左端点 => 通过第一层的长度和第二层的左端点，得到右端点 => 通过第二层的左端点和第二层推出来的右端点获得区间 => 进而枚举分割点
2、通过先枚举右端点，然后再枚举左端点，=> 获得区间，再枚举分割点
#include <iostream>
using namespace std;
#define maxn 305
int n, a[maxn], dp[maxn][maxn], ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);a[i+n]=a[i];}
for (int i = 2; i < 2*n; ++i)
for (int j = i-1; j >= 1 && i-j < n; --j)
for (int k = j; k < i; ++k) {
dp[j][i] = max(dp[j][i], dp[j][k]+dp[k+1][i]+a[j]*a[k+1]*a[i+1]);
ans = max(ans, dp[j][i]);
}
printf("%d\n", ans);
return 0;
}