自动搬运

查看原文

来自洛谷，原作者为

	hanbingchen01 **

搬运于2025-08-24 21:36:11，当前版本为作者最后更新于2019-11-11 23:24:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一翻题解，发现题解里各位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;
}