刷题记录:牛客NC50493石子合并

传送门:牛客

题目描述:

将n堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。
请编写一个程序，读入堆数n及每堆的石子数，并进行如下计算：
选择一种合并石子的方案，使得做n-1次合并得分总和最大。
选择一种合并石子的方案，使得做n-1次合并得分总和最小。
输入:
4
4 5 9 4
输出:
43
54
1
2
3
4
5
6
7
8
9
10

一道经典的区间dp题,假设没有围成一个圈的话将退化成此题,对于dp方程,直接参考上述题即可,下面主要讲一下如何处理围成环的问题

注意,因为此题的N只有200.所以可以直接使用区间dp解决,但是如果我们的N变到了1000甚至更高就需要四边形不等式优化甚至是贪心的做法了

其实对于我们的环我们有一个巧妙的方法,那就是将我们的链复制一份放在原来链的后面,想一下,这样的话是不是我们无论环是怎么变化的,我们始终都能够枚举到各个环的状态,因为无论我们的n进行一个循环和刚开始的任何位置进行合并,我们都可以将前面的几个数字移动到我们的后面来.假设不理解的话可以自行试着模拟一下.将环变成链是一种比较经典的方法

下面是具体的代码部分:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n;int dp[1000][1000];
int a[1000];int sum[1000];
int main() {
	n=read();
	for(int i=1;i<=n;i++) {
		a[i]=read();sum[i]=sum[i-1]+a[i];
	}
	for(int len=2;len<=n;len++) {
		for(int l=1;l<=n-len+1;l++) {
			int r=l+len-1;
			dp[l][r]=dp[l][l]+dp[l+1][r]+sum[r]-sum[l-1];
			for(int k=l+1;k<=r-1;k++) {
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
			}
		}
	}
	cout<<dp[1][n]<<endl;
	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