李大恕 的博客

OI蒟蒻的水坑

0%

题解 P2308【添加括号】

发表于 更新于 分类于 ， ，

P2308 添加括号

题面

题目背景

给定一个正整数序列$a_1,a_2,\cdots,a_n,(1\le n\le20)$

不改变序列中每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。

例如:

给出序列是$4,1,2,3$。

第一种添括号方法:

$((4+1)+(2+3))=((5)+(5))=(10)$

有三个中间和是$5,5,10$，它们之和为:$5+5+10=20$

第二种添括号方法

$(4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10)$

中间和是$3,6,10$，它们之和为$19$。

题目描述

现在要添上$n-1$对括号，加法运算依括号顺序进行，得到$n-1$个中间和，求出使中间和之和最小的添括号方法。

输入格式

共两行。第一行，为整数$n(1\le n\le20)$。第二行，为$a_1,a_2,\cdots,a_n$这$n$个正整数，每个数字不超过$100$。

输出格式

输出$3$行。第一行，为添加括号的方法。第二行，为最终的中间和之和。第三行，为$n-1$个中间和，按照从里到外，从左到右的顺序输出。

解析

很明显，此题是一道区间dp。（有两个点多解，数据过于毒瘤，害我调了好久，请求开启SPJ @chen_zhe）

定义状态$f[i][j]$表示区间$[i,j]$的最小的中间和之和。区间dp的状态转移是按照区间长度从小到大进行，因此$[i,j]$必然由更小的区间转移而来。当然，为了转移时更方便计算中间和，我们使用前缀和$s[i]$来存储$\sum\limits_{k=1}^ia_k$。

考虑$k\in[i,j-1]$中的任意断点$k$，可将区间分成两个部分$[i,k]$和$[k+1,j]$，那么有

即区间$[i,k]$与区间$[k+1,j]$的最小中间和之和相加，再加上当前合并得到的中间和。上述即为状态转移方程。

当然本题还需注意最后的输出：我们用$h[i][j]$来存储区间$[i,j]$的断点，每一个区间分成两段，递归输出即可。

其余详见代码。

Code

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
#include<bits/stdc++.h>
using namespace std;

int f[21][21],s[21],h[21][21];

void print1(int l,int r)			// 输出添加括号方法
{
	if(l==r){						// 区间只有一个数，输出并回溯
		cout<<s[l]-s[l-1];
		return;
	}
	cout<<'(';
	print1(l,h[l][r]);				// 输出左半段
	cout<<'+';
	print1(h[l][r]+1,r);			// 输出右半段
	cout<<')';
}

void print2(int l,int r)			// 输出中间和
{
	if(l==r)return;					// 区间只有一个数，不存在中间和，回溯
	print2(l,h[l][r]);				// 输出左半段
	print2(h[l][r]+1,r);			// 输出右半段
	cout<<s[r]-s[l-1]<<' ';			// 输出当前区间中间和
}

int main()
{
	int n,i,j,l,a;
	cin>>n;
	memset(f,0x3f,sizeof(f));
	for(i=1;i<=n;i++){
		cin>>a;
		f[i][i]=0;					// 初始化只有一个数的区间最小的中间和之和为0
		s[i]=s[i-1]+a;				// 前缀和
	}
	for(l=2;l<=n;l++)				// 第一层枚举区间长度，从2~n
		for(i=1;i<=n-l+1;i++)		// 第二层枚举区间左端点
			for(j=i;j<i+l-1;j++)	// 第三层枚举断点
				if(f[i][j]+f[j+1][i+l-1]+s[i+l-1]-s[i-1]<=f[i][i+l-1]){ // 毒瘤数据！必须写成<=才能过，<过不了
					f[i][i+l-1]=f[i][j]+f[j+1][i+l-1]+s[i+l-1]-s[i-1];	// 更新f[i][j]
					h[i][i+l-1]=j;	// 储存断点
				}
	print1(1,n);
	cout<<'\n'<<f[1][n]<<'\n';
	print2(1,n);
	return 0;
}