从合并石子学区间DP

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6
从合并石子学区间DP 区间DP是一种思考方式很不一样的DP问题。 结合合并石头进行问题思考,你就能学会区间DP啦!

image

导读 ^ _ ^

区间DP是一种思考方式很不一样的DP问题。
结合合并石头进行问题思考,你就能学会区间DP啦!

何为区间DP

其DP推导是在一个区间内进行的,通常DP数组代表某个区间的某些属性。
当然,dp数组的推导非常麻烦。
需要依据某种特定的顺序,进行dp推导。
通常是 区间长度从小到大进行状态转移

合并石子

Snipaste_2022-12-27_17-24-45.png

对于石头搬运的理解

最终的结果一定是两个合成一个,那么我们只要让合并的东西最小即可,如此递推下去。

image.png

推导状态转移

这里需要运用前缀和的思想,去舍掉无关石头的影响。
image.png

代码实现

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main( ) {
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) 
	    scanf("%d",&s[i]);
	
	//前缀和处理
	for(int i = 1; i <= n; i++) s[i] += s[i-1];
	
	//从区间长度小的开始枚举,len初始为2
	for(int len = 2; len <= n; len++) 
	   for(int i = 1; i + len -1 <= n; i++) {
	   	  int l = i, r = i + len - 1;
	   	  f[l][r] = 1e8;
	   	  for (int k = l; k < r; k++) //这里k<r
	   	      f[l][r] = min(f[l][k] + f[k+1][r] + s[r] - s[l-1],f[l][r]);
	   }
	printf("%d",f[1][n]);
	return 0;
}

#谢谢你的观看!

^ _ ^

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6