一道 区间 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
环上的区间 DP
现在让我们回到原问题，怎么处理在环上的情况呢？
如果是在一个长为 (n) 的环上，那么弄一条长为 (2n) 的链（重复一次），DP 求解后取 (f(1,n),f(2,n+1),\ldots,f(n-1,2n-1)) 中的最优值即可。时间复杂度仍为 (O(n^3))。
#include
#include
#include
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
Original: https://www.cnblogs.com/zhb2000/p/luogu-P1880.html
Author: zhb2000
Title: 洛谷 P1880 石子合并
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587653/
转载文章受原作者版权保护。转载请注明原作者出处！