[区间dp]合并石子升级版

题目描述

还记得经典题石子合并吗？现在小 $Y$ 将题目加强啦！
在一个圆形操场的四周摆放着 $n$ 堆石子，现要将石子有次序地合并成一堆。规定每次只能选取相邻的三堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
编一程序，读入石子堆数 $n$ 及每堆的石子数。选择一种合并石子的方案，使得做 $(n-1)/2$ 次合并，得分的总和最小。

输入格式

第 $1$ 行 $1$ 个数，表示石子堆数。
第 $2$ 行是顺序排列的各堆石子数（$\le 1000$），每两个数之间用空格分隔。

输出格式

输出合并的最小得分。

样例

样例输入1：

5
1 2 3 4 5

样例输出1：

21

样例1解释：
先合并 $(1,2,3)$，再合并 $(6,4,5)$。

数据范围

对于 $20\%$ 的数据，$n=5$。
对于 $60\%$ 的数据，$n\le 80$。
对于 $100\%$ 的数据，$3\le n\le 400$。

题解

由于是圆形的，所以需要破环为链，这里我直接复制一份到后面即可。

对于 $20\%$ 的数据，先合并三堆后，只剩下三堆，直接枚举即可。

对于 $60\%$ 的数据，和合并石子差不多，依然是 区间dp。
d p i , j = m i n { d p i , k 1 + d p k 1 + 1 , k 2 + d p k 2 + 1 , j + s u m j − s u m i − 1 } dp_{i, j} = min\{dp_{i, k1} + dp_{k1 + 1, k2} + dp_{k2 + 1, j} + sum_j - sum_{i - 1}\} dpi,j​=min{dpi,k1​+dpk1+1,k2​+dpk2+1,j​+sumj​−sumi−1​}。
枚举长度和左端点，计算右端点，枚举两个断点进行转移。
复杂度为 $\Theta (n^4)$。

如果这道题你写的 $60$ 分代码是 $20$ 分，可以试一下以下数据：
输入

7
1 3 4 2 5 1 5

输出

37

解释
先合并 $(1,5,1)$，再合并 $(3,4,2)$，最后合并 $(9,5,7)$。

int f[810][810];//dp
int sum[810];//前缀和
int main(){
	输入
	//破环为链
	for(int i = 1; i <= n; ++ i){
		a[i + n] = a[i];
	}
	//初始化
	for(int i = 1; i <= 2 * n; ++ i){
		f[i][i] = 0;
		f[i][i + 1] = 0x3f3f3f3f;
		f[i][i + 2] = a[i] + a[i + 1] + a[i + 2];
		sum[i] = sum[i - 1] + a[i];
	}
	//转移
	for(int l = 4; l <= n; ++ l){//长度
		for(int i = 1; i <= 2 * n - l; ++ i){//左端点
			int j = i + l - 1;//[i, j]
			//[i, k1] + [k1 + 1, k2] + [k2 + 1, j]
			f[i][j] = 0x3f3f3f3f;
			//枚举断点
			for(int k1 = i; k1 <= j; ++ k1){
				for(int k2 = k1; k2 <= j; ++ k2){
					f[i][j] = min((long long)f[i][k1] + f[k1 + 1][k2] + f[k2 + 1][j] + sum[j] - sum[i - 1], (long long)f[i][j]);
				}
			}
		}
	}
	//统计答案
	int ans = 0x3f3f3f3f;
	for(int i = 1; i <= n; ++ i){
		ans = min(ans, f[i][n + i - 1]);
	} 
} 

对于 $100\%$ 的数据，时间复杂度肯定超了。

这时我们考虑原版合并石子问题，只需要枚举一个断点，而当前枚举了两个断点。
将两个断点想成先断一处，再断一处。
先断就相当于原版合并石子问题，再断一处就从先断处理出的值和另外一边的值转移即可。
复杂度为 $\Theta (n^3)$。

int main(){
	输入，破环为链
	//预处理
	for(int i = 1; i <= 2 * n; ++ i){
		f[i][i] = 0;
		f[i][i + 1] = 1e16;
		sum[i] = sum[i - 1] + a[i];
	}
	for(int l = 3; l <= n; ++ l){
		for(int i = 1; i <= 2 * n - l; ++ i){
			int j = i + l - 1;
			f2[i][j] = f[i][j] = 1e16;
			//预处理先断
			for(int k1 = i; k1 < j; ++ k1){
				f2[i][j] = min((long long)f[i][k1] + f[k1 + 1][j], (long long)f2[i][j]);
			}
			//后断
			for(int k2 = i; k2 < j; ++ k2){
				f[i][j] = min((long long)f2[i][k2] + f[k2 + 1][j] + sum[j] - sum[i - 1], (long long)f[i][j]);
			}
		}
	}
	统计答案
}