题解 CodeVS1251 【括号】

题目描述：

计算乘法时，我们可以添加括号，来改变相乘的顺序，比如计算 $x_1,x_2,...,x_{n-1},x_n$ 的积，我们可以：

$(x_1(x_2(...(x_{n-1}x_n))))$......$((((x_1x_2)...)x_{n-1})x_n)$

你的任务是编程求出所有这样的添括号的方案。

输入格式：

输入文件第一行是一个数 $n$ $(1<=n<=10)$，表示有 $n$ 个变量，之后 $n$ 行每行一个变量的名字。

输出格式：

输出所有的添加括号的方案。注意：单个字符不要加括号，两个字符相乘中间要有乘号。

题解：

本题不难$dfs$计算答案，难的是输出答案

我们可以先从如何计算答案入手，易得，区间 $l-r$ 的方法数计算公式为：

$f(l,r)=\sum_{i=l}^{r-1}f(l,i)*f(i+1,r)$

因为答案数是由子区间得来的，所以具体答案也是从子区间得来的，我们可以定义 $ans(l,r,k)$ 为区间 $l$ 到 $r$ 的第 $k$ 个答案。如果我们是使用 $string$ 来记录答案的话答案的获得公式即为：

$ans(l,r,x)=ans(l,i,y)+ans(i+1,r,z)$，其中$(l<=i<r)(x,y,z$为任意的存在的答案下标$)$

如果担心超空间，可以尝试存储序号，将“$($”标号为 $11$ ，将“$)$”标号为 $12$ ，将“$*$”标号为 $13$ ，只不过这样就不能使用优秀的$string$来更新答案了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;
string s[15];
vector <string> ans[15][15];
void dfs(int l,int r)
{
	if(ans[l][r].size())
	return ;
	for(int i=l;i<r;++i)
	{
		dfs(l,i);
		dfs(i+1,r);
	}
	for(int i=l;i<r;++i)
	{
		for(int j=0;j<(int)ans[l][i].size();++j)
		{
			for(int k=0;k<(int)ans[i+1][r].size();++k)
			{
				ans[l][r].push_back("("+ans[l][i][j]+ans[i+1][r][k]+")");
			}
		}
	}
//	printf("%d %d\n",l,r);
//	for(int i=0;i<(int)ans[l][r].size();++i)
//	cout<<ans[l][r][i]<<‘\n‘;
	return ;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>s[i];
		ans[i][i].push_back(s[i]);
		if(i>1)
		ans[i-1][i].push_back("("+s[i-1]+"*"+s[i]+")");
	}
	dfs(1,n);
	for(int i=0;i<(int)ans[1][n].size();++i)
	cout<<ans[1][n][i]<<‘\n‘;
	return 0;
}

题解 CodeVS1251 【括号】

原文：https://www.cnblogs.com/Point-King/p/13304771.html