添加括号（区间dp+求方案）

添加括号

题目背景

给定一个正整数序列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

4
4 1 2 3

样例输出 #1

(4+((1+2)+3))
19
3 6 10

提示

范围在题目上有说明。

思路

这道题的第二小问你不觉得很熟悉吗，它不就是合并果子的板子小题吗？因此我们这道题用区间dp来做，只不过这道题相比那道题多了求方案。对于这样的，我们可以类似二叉树的中序遍历那样来找方案。

具体怎么找方案：

• 我们可以在区间dp开始枚举断点的时候，如果状态已经更新了，我们就可以记录此时状态的断点。
• 然后我们采取中序遍历的板子来写出答案。

代码

//这道题如果不求方案的话就是石子合并了
//所以，这道题就是很经典的区间合并，只不过要求方案
//对于题目的第一第三问，我们可以利用树的方式遍历（也就是中序遍历）

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 25;

int f[N][N];
int n;
int w[N];
int s[N];//前缀和
int pre[N][N];
int ans[N],cnt;

void print(int x,int y){
    if(x==y){
        cout<<s[x]-s[x-1];
        return;
    }
    
    cout<<"(";
    print(x,pre[x][y]);
    cout<<"+";
    print(pre[x][y]+1,y);
    cout<<")";
    ans[++cnt]=s[y]-s[x-1];
}

int main(){
    cin>>n;
    
    memset(f,0x3f,sizeof f);
    
    for(int i=1;i<=n;i++){
        cin>>w[i];
        s[i]=s[i-1]+w[i];
        f[i][i]=0;
    }
    
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            for(int k=l;k<r;k++){//为什么不能等于r，因为必须要有两份
                // f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
                if(f[l][k]+f[k+1][r]+s[r]-s[l-1]<f[l][r]){
                    f[l][r]=f[l][k]+f[k+1][r]+s[r]-s[l-1];
                    pre[l][r]=k;//记录分界点
                }
            }
        }
    }
    print(1,n);//中序遍历
    cout<<endl;
    cout<<f[1][n]<<endl;
    for(int i=1;i<=cnt;i++){
        cout<<ans[i]<<' ';
    }
    return 0;
}