吐槽
滚动

Luogu P2308 添加括号 题解及心得

题目背景

给定一个正整数序列a(1),a(2),…,a(n),(1<=n<=20)

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

例如:

给出序列是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< =n< =20) 第二行,为a(1),a(2),…,a(n)这n个正整数,每个数字不超过100。

输出格式:

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

输入输出样例

输入样例#1: 

输出样例#1: 

显然加括号过程是依赖最小中间和的,而最小中间和势必从一个区间中得出,故不难看出这是一个区间dp。

不难得出状态转移方程:f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1])

解题思路:

1、先区间dp,逆向枚举i,正向枚举j,阶段k=i,k<j。由于括号添加时要尽可能靠左,所以当新值<=f[i][j]时即发生更新。

//求最小值时i逆序j正序,最大值时都正序

2、为了能解决第二问和第三问,令g[i][j]=k保存从下标i~j之间断点k的位置。

3、对于第二问,递归查找每个点左边有多少个左括号,右边有多少个右括号,然后输出。

4、对于第三问,递归求每个中间和,然后输出。

心得:虽然大部分区间dp是在最外层枚举阶段,但是偶尔也要像这题这样最内层枚举阶段吧。//还有可能是我没想到最外层枚举阶段的做法(小声)。

总之,終わり!

Contents licensed under Creative Commons by-nc-sa 3.0.
Post Comment

Post Comment