本文共 1521 字，大约阅读时间需要 5 分钟。
给定一串括号串，对于其中每个左括号‘(’最多只能找到一个与之相匹配的右括号‘)’。我们可以用栈算法找出每个括号的匹配位置，存储在数组pos中。pos[i]表示第i个左括号对应的右括号的位置，初始值为-1，表示没有匹配的右括号。接下来，我们需要计算以每个括号为开头的合法括号序列的数量，存储在ans数组中。
状态转移方程为ans[i] = ans[pos[i] + 1] + 1，其中i != -1。ans[i]表示以第i个括号开头的合法括号序列的数量。最终答案是所有ans[i]的总和。
初始化：创建pos数组，初始值均为-1。创建ans数组，初始值均为0。
栈匹配括号：使用栈遍历括号字符串，记录每个左括号对应的右括号位置到pos数组中。
计算ans数组：从字符串末尾向前遍历，根据pos数组更新ans数组的值。
求总和：将ans数组中的所有值求和，得到最终答案。
#include#include using namespace std;int main() { char s[n]; int t; stack S; for (scanf("%d", &t); t--; ) { scanf("%s", s); int len = strlen(s); fill(pos, pos + len, -1); fill(ans, ans + len, 0); while (!S.empty()) { int i = S.top(); S.pop(); if (s[i] == ')') { for (int j = 0; j < len; ++j) { if (s[j] == '(' && pos[j] == -1) { pos[j] = i; break; } } } } int sum = 0; for (int i = len - 1; i >= 0; --i) { if (pos[i] != -1) { ans[i] = ans[pos[i] + 1] + 1; sum += ans[i]; } } cout << sum << '\n'; } return 0;}
初始化：使用fill函数初始化pos和ans数组，pos初始值为-1，ans初始值为0。
栈匹配括号：遍历字符串，使用栈记录左括号的位置。当遇到右括号时，弹出栈顶的左括号位置，并将其记录到pos数组中。
计算ans数组：从字符串末尾向前遍历，计算每个左括号对应的合法括号序列数量。ans[i] = ans[pos[i] + 1] + 1，表示以i为起点的括号序列数等于其后续可能的括号数加上空的情况。
求总和：将ans数组中的所有值求和，得到最终答案，并输出。
通过这种方法，可以高效地计算出每个左括号开头的合法括号序列数量，并求出总和，解决问题。
转载地址：http://rkokz.baihongyu.com/