codevs1251 括号
2024-08-24 10:52:42
1251 括号
时间限制: 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)
思路
深搜
首先设一个动态数组vector<string>ans[11][11]。a[i][j][k]表示首单词为i,末单词为j的单词串的总种类集合。
递归的思想。从大范围往小范围紧缩,也就是从整体(1到n的单词串总种类集合)二分,先找到左侧的种类再找右侧种类,最后进行拼接。
代码
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
vector<string>ans[][];
int n;
string s[];
void dfs(int l,int r)
{
if(ans[l][r].size())return;
if(l==r)
ans[l][l].push_back(s[l]);
else{
for(int i=l;i<=r;i++)
{
dfs(l,i);
dfs(i+,r);
int n1=ans[l][i].size(),n2=ans[i+][r].size();
for(int j=;j<n1;j++)
{
for(int k=;k<n2;k++)
{
string s;
s="("+ans[l][i][j];
if(r-l==)
s+="*";
s+=(ans[i+][r][k]+")");
ans[l][r].push_back(s);
}
}
}
}
}
int main()
{
cin>>n;
for(int i=;i<=n;i++)cin>>s[i];
dfs(,n);
int m=ans[][n].size();
for(int i=;i<m;i++)
cout<<ans[][n][i]<<endl;
}
最新文章
- python 实现简单 http 代理
- Linux_Shell_输出重定向
- J2SE 1.6 特性:java.lang.instrument
- Scrum Meeting---Eleven(2015-11-6)
- C语言知识整理(3):内存管理(详细版)
- inputstream和outputstream读写数据模板代码
- Android Wear计时器开发
- /etc/fstab自动挂载文件系统
- R语言画正弦曲线
- BNUOJ flower (搜索)
- [速成]了解一致性hash算法
- 201621123027 《Java程序设计》第1周学习总结
- MQTT初步使用
- IO复用\阻塞IO\非阻塞IO\同步IO\异步IO
- Show tree of processes in linux
- linux shell创建目录、遍历子目录
- 奔跑吧Linux
- 转:iOS7导航栏遮盖问题的解决
- 异步消息框架netty
- sqlserver-一次updlock和withnolock和with check option 的报错原因分析
热门文章
- 关于Spring注解 @Service @Component @Controller @Repository 用法
- Oracle伪列rownum
- swift中反向循环
- debian下编译openwrt固件
- 《avascript 高级程序设计(第三版)》 ---第三章 基本概念2
- 郝健: Linux内存管理学习笔记-第2节课【转】
- Sql 工资第二高(考虑并列)
- input标签添加上disable属性在移动端字体颜色不兼容的解决办法。
- 分享知识-快乐自己:SpringMvc中 页面日期格式到后台的类型转换
- codeforces 609D D. Gadgets for dollars and pounds(二分+贪心)