P2308 添加括号 题解

· · 题解

一翻题解，发现题解里各位DALAO输出带括号的表达式时都先

递归计算左右括号个数，然后循环输出

我的方法比较好理解一些

首先

第一步：DP

设 dp[i][j] 表示从第 i 个数到第 j 个数添加 j-i+1 对括号

所能通过每一步加法得到的最优值。

那么问题来了，状态转移方程怎么列？

我们可以这么来想：

dp[i][j] 怎么得来

经过前面的计算，我们已经把第i-第j个数合并成了两个数

那么我们需要一个k(i<=k<j)来枚举合并的是哪俩个部分，

也就是加号的位置。随之，方程就出来了：

dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])

sum[i]表示的是前i个数之和（前缀和）

接下来是输出

我们用 jiahao[i][j] 表示区间i-j 最优解之加号的位置

我们可以把一个表达式看作一棵树，递归输出这一棵树，其中可以近似地把加号看成根，两边表达式分别是左右子树

然后在递归函数里这样写：

void print(long long int l,long long int r)
{
    if(l==r)
    {
        cout<<shu[l];
        return;
    }
    cout<<"(";//输出括号
    print(l,jiahao[l][r]);//输出加号右边表达式
    cout<<"+";//输出加号
    print(jiahao[l][r]+1,r);//输出加号左边表达式
    cout<<")";//输出括号
}

那么下一步计算过程，其实和输出表达式很像，直接看代码

long long int jisuan(long long int l,long long int r)
{
    if(l==r)retur
    n shu[l];
    long long int temp=jisuan(l,jiahao[l][r])+jisuan(jiahao[l][r]+1,r);
    cout<<temp<<" ";
    return temp;
}

完整代码如下

#include<iostream>
#include<algorithm>
using namespace std;
long long int n,shu[50],sum[50],dp[50][50],jiahao[50][50];
long long int jisuan(long long int l,long long int r)
{
    if(l==r)retur
    n shu[l];
    long long int temp=jisuan(l,jiahao[l][r])+jisuan(jiahao[l][r]+1,r);
    cout<<temp<<" ";
    return temp;
}
void print(long long int l,long long int r)
{
    if(l==r)
    {
        cout<<shu[l];
        return;
    }
    cout<<"(";
    print(l,jiahao[l][r]);
    cout<<"+";
    print(jiahao[l][r]+1,r);
    cout<<")";
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>shu[i];
        sum[i]=sum[i-1]+shu[i];
    }
    for(int l=2;l<=n;l++)
    {
        for(int i=1;i+l-1<=n;i++)
        {
            int j=i+l-1;
            dp[i][j]=0x7fffffffff;
            for(int k=j-1;k>=i;k--)
            {
                if(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]<dp[i][j])
                {
                    dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                    jiahao[i][j]=k;
                }
            }
        }
    }
    print(1,n);
    cout<<endl;
    cout<<dp[1][n]<<endl;
    long long int temp=jisuan(1,n);
    return 0;
}