【动态规划】石子合并问题_石子合并问题动态规划

1.题目描述

2.算法思路(以求最小得分为例，求最大得分同理)

1、算法总体思路类似于矩阵连乘问题，可以用dp[i][j]表示：合并第i堆到第j堆的最少得分

2、但它们之间最大的区别是：此题为一个圆形操场——首尾相接，第一堆和最后一堆也是相邻的。故需要增加一维数据分别记录两种合并情况，如下图：

• 第一种情况是合并i~j
• 第二种情况是合并1~i，j~n

3.最后枚举最后两堆的合并情况得到最小得分

3.程序代码

#include<bits/stdc++.h>
using namespace std;
#define N 100 
int n;
int a[N],sum[N];
int dp_min[N][N][2]; //dp_min[i][j][0]：合并i~j   dp_min[i][j][1]:合并j~n 1~i  
int dp_max[N][N][2]; 
int main(){
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i]; //sum[i]：前i堆石子的和		
	}
	memset(dp_min,0x3f,sizeof(dp_min));
	//单堆石子不需要合并
	for(int i=1;i<=n;i++) {
		dp_min[i][i][0]=0;
		dp_max[i][i][1]=0; 
	}
	//r表示连续合并的石子堆数 
	for(int r=2;r<=n;r++){
		//i表示起始石堆号 
		for(int i=1;i<=n-r+1;i++){
			int j=i+r-1; //J表示终止石堆号
			for(int k=i;k<j;k++){
				dp_min[i][j][0]=min(dp_min[i][j][0],dp_min[i][k][0]+dp_min[k+1][j][0]+sum[j]-sum[i-1]);
				dp_max[i][j][0]=max(dp_max[i][j][0],dp_max[i][k][0]+dp_max[k+1][j][0]+sum[j]-sum[i-1]);				 
			} 
		}
	}
	for(int r=2;r<n;r++){
		for(int j=n;j+r-1-n>=1;j--){
			int i=j+r-1-n; 
			int A=sum[i]+sum[n]-sum[j-1];
			dp_min[i][j][1]=dp_min[j][n][0]+dp_min[1][i][0]+A;
			dp_max[i][j][1]=dp_max[j][n][0]+dp_max[1][i][0]+A;
			for(int k=1;k<i;k++){
				dp_min[i][j][1]=min(dp_min[i][j][1],dp_min[k][j][1]+dp_min[k+1][i][0]+A);
				dp_max[i][j][1]=max(dp_max[i][j][1],dp_max[k][j][1]+dp_max[k+1][i][0]+A);				 
			}
			for(int k=j;k<n;k++){
				dp_min[i][j][1]=min(dp_min[i][j][1],dp_min[i][k+1][1]+dp_min[j][k][0]+A);
				dp_max[i][j][1]=max(dp_max[i][j][1],dp_max[i][k+1][1]+dp_max[j][k][0]+A);				
			} 
		}
	}
	int ans_min=dp_min[1][n][0];
	int ans_max=dp_max[1][n][0];
	for(int i=2;i<n;i++){
		for(int j=i;j<n;j++){
			ans_min=min(ans_min,dp_min[i][j][0]+dp_min[i-1][j+1][1]+sum[n]);
			ans_max=max(ans_max,dp_max[i][j][0]+dp_max[i-1][j+1][1]+sum[n]);
		}
	}	 
	printf("%d\n%d",ans_min,ans_max);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

4.生成测试数据

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	freopen("input.txt","w",stdout);
	srand(time(0));
	for(int i=0;i<n;i++) printf("%d ",rand());
    fclose(stdout);
}
1
2
3
4
5
6
7
8
9
10
11
12

5.不同规模数据实验的时间对比

计时方式:

#include<windows.h>	
	...
LARGE_INTEGER nFreq,nBegin,nEnd;
QueryPerformanceFrequency(&nFreq);	
QueryPerformanceCounter(&nBegin);
...//需要计算运行时间的关键代码
QueryPerformanceCounter(&nEnd);
double t=(double)(nEnd.QuadPart-nBegin.QuadPart)/(double)nFreq.QuadPart; //得到运行时间t
printf("运行时间：%lf",t);
1
2
3
4
5
6
7
8
9

6.时间复杂度分析

最多三层循环

O(n3)