[复习资料.PDF]环形石子合并(DP)

discription:
有一圈石子, 每堆重量为w[i], 每次操作合并相邻的石子, 得分为两堆石子的重量之和. 问将这一圈n个石子合并n-1次成一堆的最高和最低得分.
solution:
将环展开成链:\(12345 \rightarrow 1234512345\), 复制后, 双倍链中有环的所有排列.
前缀和预处理获取\(i到j\)的重量和\(sum(i,j)\)
DP:
\(设起点i,终点j的最少得分为f[i,j], 则f[i,j]=\begin{cases} min_{i\le k<j}(f[i,k]+f[k+1,j]+sum(i,j)) \ 0, \ when \ \ i=j \end{cases}\)
将区间长度\(d\)作为外层循环, 以建立递推.
code:

#include<cstdio>
#include<cstring>
const int INF(1000000000);
int M[202][202], m[202][202], w[202], sum[202];
inline int s(const int& i, const int& j) { return sum[j] - sum[i - 1]; }
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", w + i);
		w[i + n] = w[i];
	}
	for (int i = 1; i < (n << 1); ++i)sum[i] = sum[i - 1] + w[i];
	for (int d = 1; d < n; ++d) 
		for (int i = 1, j = i + d; j<(n<<1); j = ++i + d) {
			M[i][j] = 0, m[i][j] = INF;
			for (int k = i; k < j; ++k) {
				if (M[i][k] + M[k + 1][j] + s(i, j) > M[i][j])M[i][j] = M[i][k] + M[k + 1][j] + s(i, j);
				if (m[i][k] + m[k + 1][j] + s(i, j) < m[i][j])m[i][j] = m[i][k] + m[k + 1][j] + s(i, j);
			}
		}
	int Max=0, Min=INF;
	for (int i = 1; i <= n; ++i) {
		if (Max < M[i][i + n - 1])Max = M[i][i + n - 1];
		if (Min > m[i][i + n - 1])Min = m[i][i + n - 1];
	}
	printf("%d %d\n", Max, Min);
}

[复习资料.PDF]环形石子合并(DP)

原文：https://www.cnblogs.com/dwt2021/p/14403721.html