AcWing算法提高课：动态规划6-区间DP

摘要

1068. 环形石子合并 - AcWing题库：区间DP + 断环成链 + 前缀和

320. 能量项链 - AcWing题库：区间DP + 断环成链

479. 加分二叉树 - AcWing题库：区间DP + 二叉树遍历

1069. 凸多边形的划分 - AcWing题库：区间DP + 三角剖分 + 高精度

321. 棋盘分割 - AcWing题库：二维区间DP

1068 环形石子合并

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：

• 选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
• 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

题解

最小值状态转移方程： \[ dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + \sum_{l}^{r}a[i]) \] 最大值状态转移方程： \[ dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + \sum_{l}^{r}a[i]) \] \(dp[l][r]\) 表示合并 l 到 r 个石子需要的花销。此处，遍历划分点k，可以得到每个区间的最优解。

注意：这里的求和需要用前缀和优化。

代码

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 500;

int n,a[maxn],prefix[maxn];
int dp1[maxn][maxn],dp2[maxn][maxn];
int ma,mi;

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		cin>>a[i]; a[i+n] = a[i];
	}
	for(int i = 1 ; i <= 2*n ; i ++){
		prefix[i] = prefix[i-1] + a[i];
	}
	memset(dp1,inf,sizeof(dp1));
	memset(dp2,-inf,sizeof(dp2));
	for(int i = 1 ; i <= 2*n ; i ++){
		dp1[i][i] = dp2[i][i] = 0;
	}
	for(int i = 2 ; i <= n ; i ++){
		for(int j = 1; j+i-1 < 2*n ; j ++){
			int l = j;
			int r = j+i-1;
			int sum = prefix[r] - prefix[l-1];
			for(int k = l ; k < r;  k ++){
				dp1[l][r] = min(dp1[l][r], dp1[l][k] + dp1[k+1][r] + sum);
				dp2[l][r] = max(dp2[l][r], dp2[l][k] + dp2[k+1][r] + sum);
			}
		}
	}
	ma = -inf; mi = inf;
	for(int i = 1 ; i+n-1 < 2*n ; i ++){
		mi = min(mi, dp1[i][i+n-1]);
		ma = max(ma, dp2[i][i+n-1]);
	}
	cout<<mi<<"\n"<<ma;
	return 0;
}

320 能量项链

如果前一颗能量珠的头标记为 m，尾标记为 r，后一颗能量珠的头标记为 r，尾标记为 n，则聚合后释放的能量为 m×r×n，新产生的珠子的头标记为 m，尾标记为 n。

例如：((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710

显然，不同的聚合顺序得到的总能量是不同的，请求出一串项链释放出的最大总能量。

题解

\[ dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r] + h[l]*h[k+1]*h[r+1]) \]

\(dp[l][r]\) 表示合并 l 到 r 个珠子释放出的最大能量，\(h[i]\)表示某个珠子的头标记，\(h[i+1]\)恰好是尾标记。

此处，遍历划分点k，可以得到每个区间的最大值。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 205;

int n,ans;
int h[maxn],dp[maxn][maxn];

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		cin>>h[i];
		h[i+n] = h[i];
	}
	for(int i = 2 ; i <= n ; i ++){
		for(int j = 1 ; j+i-1 < 2*n ; j ++){
			int l = j;
			int r = j+i-1;
			for(int k = l ; k < r ; k ++){
				dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r] + h[l]*h[k+1]*h[r+1]);
			}
		}
	}
	for(int i = 1 ; i+n-1 < 2*n ; i ++){
		ans = max(ans,dp[i][i+n-1]);
	}
	cout<<ans;
	return 0;
}

479 加分二叉树

在一颗二叉树tree中，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下：     

subtree的左子树的加分 × subtree的右子树的加分 ＋ subtree的根的分数 

tree的中序遍历为（1,2,3,…,n），现在给定每个节点的加分，要求输出： 

（1）tree的最高加分 

（2）tree的前序遍历

题解

状态转移方程： \[ dp[l][r] = dp[l][k-1]*dp[k+1][r] + w[k]; \] 此处，\(dp[l][r]\)表示从区间\([l, r]\)的最优解。 由于中序遍历的特殊性质，划分区间的点k恰好是子树的根，

我们在状态转移的过程中，记录最优解下的根为\(root[l][r]\)，最后可以重构二叉树，输出前序遍历。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;

int n,cnt;
int w[maxn], pre[maxn], dp[maxn][maxn], root[maxn][maxn];

void pre_order(int l, int r){
	if(l > r) return;
	int k = root[l][r];
	cout<<k<<" ";
	pre_order(l, k-1);
	pre_order(k+1, r);
}

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		cin>>w[i];
		dp[i][i] = w[i];
		root[i][i] = i;
	}
	for(int i = 2 ; i <= n ; i ++){
		for(int j = 1 ; j+i-1 <= n ; j ++){
			int l = j;
			int r = j+i-1;
			for(int k = l ; k < r ; k ++){
				int lt = k-1 >= l ? dp[l][k-1] : 1;
				int rt = k+1 <= r ? dp[k+1][r] : 1;
				if(lt*rt + w[k] > dp[l][r]){
					dp[l][r] = lt*rt + w[k];
					root[l][r] = k;
				}
			}
		}
	}
	cout<<dp[1][n]<<"\n";
	pre_order(1,n);
	return 0;
}

1069 凸多边形的划分

给定一个具有 N 个顶点的凸多边形，每个顶点的权值都是一个正整数。

将这个凸多边形划分成 N−2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。

题解

对于一个区间为[l, r]的N边形，都可以用一个内部的三角形（三个点），将其划分为3部分：

即 l、r和k构成的三角形 + 区间[l, k]的最优解 + 区间[k, r]的最优解。

若我们得到两个点l 和 r，第三个点k有N-2种选择，依次遍历每个选择下的权值，可以得到最优解。 \[ dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + w[l]*w[k]*w[r]) \] 注意：本题数值较大，需要使用高精度乘法和加分。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;

int n;
string w[maxn];
string dp[maxn][maxn];
int a[1000],b[1000],c[1000];

string mul(string x, string y) {
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	string ans = "";
	int la = x.length();
	int lb = y.length();
	int lc = la + lb;
	
	for (int i = 0; i < la; i++) a[i] = x[la - i - 1] - '0';
	for (int i = 0; i < lb; i++) b[i] = y[lb - 1 - i] - '0';

	for (int i = 0; i < la; i++) {
		for (int j = 0; j < lb; j++) {
			c[i + j] += a[i] * b[j];
			c[i + j + 1] += c[i + j] / 10;
			c[i + j] %= 10;
		}
	}
	while ((c[lc - 1] == 0) && (lc > 1)) lc--;
	for (int i = lc- 1; i >= 0; i--){
		ans.push_back(c[i] + '0');
	}
	return ans;
}

string add(string x, string y) {
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	int la = x.length();
	int lb = y.length();
	int lc = max(la, lb); 
	for (int i = 0; i < la; i++) a[i] = x[la - i - 1] - '0';
	for (int i = 0; i < lb; i++) b[i] = y[lb - 1 - i] - '0';
	for (int i = 0; i < lc; i++) {
		c[i] += a[i] + b[i];
		c[i + 1] += c[i]/10;
		c[i] %= 10;
	}
	lc++;
	while (lc > 1 && c[lc-1] == 0) lc--;
	string res = "";
	for (int i = lc-1; i >= 0; i--){
		res.push_back(char(c[i] + '0'));
	}
	return res;
}

string Min(string x, string y){
	int lx = x.size();
	int ly = y.size();
	if(lx > ly) return y;
	else if(ly > lx) return x;
	else{
		for(int i = 0 ; i < lx ; i ++){
			if(x[i] < y[i]) return x;
			else if(x[i] > y[i]) return y;
		}
	}
	return x;
}

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		cin>>w[i];
	}
	for(int i = 3 ; i <= n ; i ++){
		for(int j = 1 ; j+i-1 <= n ; j ++){
			int l = j;
			int r = j+i-1;
			for(int k = l+1 ; k < r ; k ++){
				string sum = mul(mul(w[l],w[k]),w[r]);
				if(dp[l][r].empty()) dp[l][r] = add(dp[l][k], add(dp[k][r], sum));
				else dp[l][r] = Min(dp[l][r], add(dp[l][k], add(dp[k][r], sum)));
			}
		}
	}
	cout<<dp[1][n];
	return 0;
}