区间 DP + 石子合并

区间 DP

区间 DP 是对一个区间的合并的代价的最优值。通常区间 \(DP\) 符合以下几个特点:

  • 合并:即将两个或多个部分进行整合,当然也可以反过;
  • 特征:能将问题分解为能两两合并的形式;
  • 求解:对整个问题设最优值,枚举合并点,将问题分解为左右两个部分,最后合并两个部分的最优值得到原问题的最优值。

一般设 \(f[i][j]\) 为把 \(i\) 到 \(j\) 的元素合并起来所需要的代价,状态转移方程

​ $$f[i][j] = \max(f[i][k],f[k+1][j])$$

这里找一道很经典的题目来看一下区间 DP + 石子合并

题目

链接传送门

石子合并

题目描述

在一个圆形操场的四周摆放 \(N\) 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。

试设计出一个算法,计算出将 \(N\) 堆石子合并成 \(1\) 堆的最小得分和最大得分。

输入格式

数据的第 \(1\) 行是正整数 \(N\),表示有 \(N\) 堆石子。

第 \(2\) 行有 \(N\) 个整数,第 \(i\) 个整数 \(a_i\) 表示第 \(i\) 堆石子的个数。

输出格式

输出共 \(2\) 行,第 \(1\) 行为最小得分,第 \(2\) 行为最大得分。

数据范围

​ \(1≤N≤100,0≤ai≤200\leq a_i\leq 200≤ai≤20。\)

思路

这道题的状态转移方程为 \(f[i][j] = \max(f[i][j],f[i][k]+f[k][j] + \sum\limits_{t=1}^j a_t)\)

这一题是很经典的区间 DP 题,但是这里有一点不一样:不是一个区间了,而是一个环了,这样就会导致终点与起始点重合(同一个点),所以我们可以枚举断开点,再对每个进行 \(dp\),一共有 \(n\) 个断开点,所以时间复杂度是 \(\mathcal{O}(n^5)\) 会超时,不可取。区间 DP + 石子合并

这时候我们想到想要把环变成一个链,还可以把这个我们将这条链延长两倍;变成 \(2 \times n\) 堆,其中第 \(i\) 堆与第 \(n \times i\) 堆相同,然后再进行动态规划。

最后再找 \(f[i][i+n-1]\) 中的最大值(最小值),就是最大值(最小值)的答案。时间复杂度为 \(\mathcal{O}(n^4)\),还是有点慢,可以用前缀和来优化,最终时间复杂度为 \(\mathcal{O}(n^3)\) ,最终的状态转移方程为:

\[f[i][j] = \max(f[i][j],f[i][k]+f[k][j] + sum[j]-sum[i-1]) \]

AC 代码

 #include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;
int dp[400][400] = {0},dp2[400][400] = {0},a[200],sum[300] = {0};

int main()
{
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[n+i] = a[i];
	}
	
	for(int i=1;i<=n+n;i++)
		sum[i] = sum[i-1] + a[i];

	for(int i=1;i<=300;i++)
		for(int j=1;j<=300;j++)
			dp2[i][j] = 9999999;    \\求 min 时必须初始化为较大值
	
	for(int i=0;i<=2*n;i++) dp2[i][i]=0;	

    //核心代码
	for (int len = 1; len <= n; len++)
	  for (int i = 1; i <= 2 * n - 1; i++) {
	    int j = len + i - 1;
	    for (int k = i; k < j && k <= 2 * n - 1; k++){
	      dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
	      dp2[i][j] = min(dp2[i][j],dp2[i][k] + dp2[k+1][j] + sum[j] - sum[i-1]);
	  	}
	}
	
	int maxn = -1;
	int minn=9999999;  
	for(int i=1;i<=n;i++){
		maxn = max(maxn,dp[i][n+i-1]);
		minn = min(minn,dp2[i][n+i-1]);
	}
	
	printf("%d\n%d\n",minn,maxn);
	return 0;	
} 
上一篇:golang源码(0) ---- go/src/time.go 中的常量


下一篇:【选择题】 (D24 0522)