首页 > 代码库 > COdevs 1251 括号

COdevs 1251 括号

2024-08-26 09:28:54   219人阅读

时间限制: 1 s　　　　空间限制: 128000 KB　　　　题目等级 : 黄金 Gold
题目描述 Description

计算乘法时，我们可以添加括号，来改变相乘的顺序，比如计算X1, X2, X3, X4, …, XN的积，可以

(X1(X2(X3(X4(...(XN-1*XN)...)))))

:::

:::

(((...(((X1*X2)X3)X4)...)XN-1)XN)

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

4

North 

South 

East 

West

样例输出 Sample Output

(North(South(East*West)))

(North((South*East)West))

((North*South)(East*West))

((North(South*East))West)

(((North*South)East)West)

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<vector> 5  6 using namespace std; 7 vector<string> dfs(string *ss,int begin,int end) 8 { 9     vector<string> ret;10     if(begin>end) return ret;11     if(begin==end)12     {13         ret.push_back(ss[begin]);14         return ret;15     }16     if(begin+1==end)17     {18         string s=‘(‘+ss[begin]+‘*‘+ss[end]+‘)‘;//最中间的合并 19         ret.push_back(s);20         return ret;21     }22     int size1,size2;23     for(int i=begin;i<end;i++)24     {25         vector<string> s1=dfs(ss,begin,i);26         vector<string> s2=dfs(ss,i+1,end);27         size1=s1.size();size2=s2.size();28         for(int j=0;j<size1;j++)29         {30             for(int k=0;k<size2;k++)31             {32                 string s=‘(‘+s1[j]+s2[k]+‘)‘;// 注意题目中说这里是没有乘号的   后续的合并 33                 ret.push_back(s);34             }35         }36     }37     return ret;38 }39 int main()40 {41     string ss[15];42     int n;43     scanf("%d",&n);44     for(int i=1;i<=n;i++)45       cin>>ss[i];46     vector<string> ans=dfs(ss,1,n);47     int size=ans.size();48     for(int i=0;i<size;i++)49         cout<<ans[i]<<endl;50     return 0;51 }

 

 

COdevs 1251 括号


联系
我们