题目描述 给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,当添加完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果。 两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括号。 例如,对于括号序列 ((()(((),只需要添加两个括号就能让其合法,有以下几种不同的添加结果:()()()()()()、()(())()(())、(())()(())()、(()())(()()) 和 ((()))((()))。 输入描述 输入一行包含一个字符串 s,表示给定的括号序列,序列中只有左括号和右括号。 输出描述 输出一个整数表示答案,答案可能很大,请输出答案除以 10000000071000000007 (即 10^9 + 7)10 9 +7) 的余数。 输入输出样例
时间: 2023-05-25 15:05:22 浏览: 37
输入 #1 复制
(()((()
输出 #1 复制
5
输入 #2 复制
)))))
输出 #2 复制
1
说明
对于样例一,我们只需要在第一位和第七位加上左括号,可以得到以下 5 种合法的括号序列: (()((())), (())((())), (()(()())), (()()(())), (()(()))()。
对于样例二,只需要在前面添加 4 个左括号,即可得到合法的括号序列:(((((())))))。
相关问题
请用c++写出一下题目代码及其注释:题目描述 给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,当添加完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果 两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括号。 例如,对于括号序列(((),只需要添加两个括号就能让其合法,有以下几种不同的添加结果:()()()、()(())、(())()、(()())和((())) 输入描述 输入一行包含一个字符串 s,表示给定的括号序列,序列中只有左括号和右括号。 输出描述 输出一个整数表示答案,答案可能很大,请输出答案除以1000000007(即 10°+ 7)的余数。
/**
* 题目描述:
* 给定一个括号序列,要求尽可能少地添加若干括号使得括号序列变得合法,
* 当添加完成后,会产生不同的添加结果,请问有多少种本质不同的添加结果
* 两个结果是本质不同的是指存在某个位置一个结果是左括号,而另一个是右括号。
* 例如,对于括号序列(((),只需要添加两个括号就能让其合法,有以下几种不同的添加结果:
* ()()()、()(())、(())()、(()())和((()))
*
* 输入:
* 输入一行包含一个字符串 s,表示给定的括号序列,序列中只有左括号和右括号。
*
* 输出:
* 输出一个整数表示答案,答案可能很大,请输出答案除以1000000007(即 10^9 + 7)的余数。
*/
#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int dp[205][205];
int main() {
char s[205];
scanf("%s", s);
int len = strlen(s);
memset(dp, 0, sizeof(dp));
for (int i = 1; i < len; i += 2) {
for (int j = 0; j + i < len; j += 2) {
if ((s[j] == '(' && s[j + i] == ')') || (s[j] == '[' && s[j + i] == ']')) {
dp[j][j + i] = dp[j + 1][j + i - 1] + 2;
for (int k = j; k < j + i; k += 2) {
dp[j][j + i] = (dp[j][j + i] + dp[j][k] * dp[k + 1][j + i]) % MOD;
}
}
}
}
printf("%d", dp[0][len - 1]);
return 0;
}
给定一个只包含小括号的序列,它们有的是匹配的,有的不匹配。请你在这个序列中加入若干个左括号或右括号后使之匹配,并让添加后的序列长度尽可能短。
假设原序列长度为n,那么最多需要添加n/2个左括号或右括号才能使其匹配。因此,我们可以考虑暴力枚举添加的左括号和右括号的个数,然后判断是否能够使序列匹配。
具体来说,我们可以从左到右遍历原序列,用一个计数器cnt记录当前未匹配的左括号的个数,如果遇到一个左括号,我们就将cnt加1,如果遇到一个右括号,我们就将cnt减1。如果在遍历的过程中,cnt的值小于0,说明当前的右括号没有与左括号匹配,需要添加一个左括号来与之匹配。遍历结束后,如果cnt的值大于0,说明存在未匹配的左括号,需要添加相应数量的右括号来与之匹配。
注意到添加的左括号和右括号的顺序对结果是没有影响的,因此我们可以先尝试添加左括号,再尝试添加右括号,取两种情况中长度更短的序列作为最终结果。
下面给出具体的实现代码:
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)