感觉看到交换就应该要想到逆序对。
思路
一个前置小知识，我们把一个排列用相邻交换复原的最小次数是逆序对数量。
考虑没有 ox 的情况。
我们顺着扫一遍字符串。
把左括号正一，右括号看作负一，当前缀和小于零以后，我们把后面最近的左括号提过来，这样可以构造出交换次数最少的合法括号串。
假如有了 ox 怎么办。
我们可以现忽略 ox 用上面的部分求出交换次数。
考虑剩下的两种次数：
-
o与x。我们发现我们永远不会交换
o和x，因为这样没有意义，当我们把一个x移到括号中间时，如果要交换o和x，那这样不如把括号移过来。 -
ox与括号。这一部分我们可以使用动态规划直接求出最优的方案。注意
x一定得在一对括号中间。
时间复杂度：\(O(|S|^2)\)。
Code
#include <bits/stdc++.h>
using namespace std;
int ans;
int d[8080];
int f[8080][8080];
int v1[8080][8080];
int v2[8080][8080];
string s, t;
int main() {
cin >> s, t = s;
int num = 0;
for (int i = 0; i < s.length(); i++) d[i] = i;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ')') num--;
if (s[i] == '(') num++;
if (num < 0) {
if (s[i] == ')') num++;
if (s[i] == '(') num--;
int k = 0;
for (int j = i; j < s.length(); j++) {
if (s[j] == '(') { k = j; break; }
}
for (int j = k; j > i; j--) {
if (s[j - 1] == '(') ans++;
if (s[j - 1] == ')') ans++;
swap(s[j], s[j - 1]);
swap(d[j], d[j - 1]);
}
if (s[i] == ')') num--;
if (s[i] == '(') num++;
}
}
vector<int> a;
vector<int> b;
vector<int> c;
num = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == ')') num--, a.push_back(d[i]), c.push_back(num);
if (s[i] == '(') num++, a.push_back(d[i]), c.push_back(num);
if (s[i] == 'o') b.push_back(d[i]);
if (s[i] == 'x') b.push_back(d[i]);
}
for (int j = 0; j < b.size(); j++) {
v1[j][0] = 0;
for (int i = 1; i <= a.size(); i++) {
v1[j][i] = (b[j] < a[i - 1]) + v1[j][i - 1];
}
}
for (int j = 0; j < a.size(); j++) {
v2[j][0] = 0;
for (int i = 1; i <= b.size(); i++) {
v2[j][i] = (a[j] < b[i - 1]) + v2[j][i - 1];
}
}
for (int i = 0; i <= a.size(); i++)
for (int j = 0; j <= b.size(); j++)
f[i][j] = 1e9;
f[0][0] = 0;
for (int i = 0; i <= a.size(); i++) {
for (int j = 0; j <= b.size(); j++) {
if (i < a.size()) f[i + 1][j] = min(f[i + 1][j], f[i][j] + v2[i][j]);
if (j < b.size()) {
if (t[b[j]] == 'o')
f[i][j + 1] = min(f[i][j + 1], f[i][j] + v1[j][i]);
if (t[b[j]] == 'x' && (i && c[i - 1]))
f[i][j + 1] = min(f[i][j + 1], f[i][j] + v1[j][i]);
}
}
}
cout << ans + f[a.size()][b.size()] << "\n";
}