主要思路来自 huzhaoyang 大佬
对于两个字符串 \(s\) 和 \(t\)（保证其中每一种字符个数相同），定义 \(s\) 和 \(t\) 的相对逆序对数为 \(s\) 得到 \(t\) 的最少交换次数，显然同种字符相对顺序保持不变，因此即依次编号后的逆序对数。
问题不妨看作构造合法字符串 \(t\) 使得 \(s\) 和 \(t\) 的相对逆序对数最小，定义 \(f_S(s)\) 为 \(s\) 仅保留 \(S\) 中的字符后所得到的字符串，那么有以下两个结论：
结论 \(1\)：当 \(S=\left\{(,)\right\}\) 时，若 \(t\) 是使得 \(s\) 和 \(t\) 相对逆序对数最小的合法字符串，则 \(f_S(t)\) 也是使得 \(f_S(s)\) 和 \(f_S(t)\) 相对逆序对数最小的合法字符串
结论 \(2\)：当 \(S=\left\{o,x\right\}\) 时，若 \(t\) 是使得 \(s\) 和 \(t\) 相对逆序对数最小的合法字符串，则 \(f_S(s)=f_S(t)\)。
由此，不妨先求出 \(S=\left\{(,)\right\}\) 时的 \(f_S(t)\)，进而即将 \(o\) 和 \(x\) 从左到右依次插入，显然这可以用一个二维 DP 计算，条件为 \(x\) 之前左括号数严格大于右括号数，计算答案考虑逆序对数即可。
虽然但是我不会证结论。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 8005;
int n, n1, n2;
int ans;
int p1[N], p2[N];
char s[N], s1[N], s2[N];
int f[N][N];
int pre1[N], pre2[N], preo[N], prex[N];
int sum1[N], sum2[N], sumo[N], sumx[N];
void chkmin(int &a, int b) { if (a > b) a = b; }
int main() {
scanf("%s", s + 1), n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
if (s[i] > 'a') s2[++n2] = s[i], p2[n2] = i;
else s1[++n1] = s[i];
pre1[i] = pre1[i - 1] + (s[i] == '(');
pre2[i] = pre2[i - 1] + (s[i] == ')');
preo[i] = preo[i - 1] + (s[i] == 'o');
prex[i] = prex[i - 1] + (s[i] == 'x');
}
for (int i = 1, cur = 0; i <= n1; ++i) {
if (s1[i] == '(') ++cur; else --cur;
if (cur < 0) {
cur = 1;
for (int j = i + 1; j <= n1; ++j) if (s1[j] == '(') {
swap(s1[i], s1[j]), ans += j - i; break;
}
}
}
for (int i = 1, P1 = 0, P2 = 0; i <= n1; ++i) {
if (s1[i] == '(') {
do {
++P1;
} while (s[P1] != '(');
p1[i] = P1;
}
else {
do {
++P2;
} while (s[P2] != ')');
p1[i] = P2;
}
}
for (int i = 1; i <= n1; ++i) {
sum1[i] = sum1[i - 1] + (s1[i] == '(');
sum2[i] = sum2[i - 1] + (s1[i] == ')');
}
for (int i = 1; i <= n2; ++i) {
sumo[i] = sumo[i - 1] + (s2[i] == 'o');
sumx[i] = sumx[i - 1] + (s2[i] == 'x');
}
memset(f, 0x3f, sizeof f), f[0][0] = 0;
for (int i = 0, cur = 0; i <= n1; ++i) {
for (int j = 0; j <= n2; ++j) {
if (i < n1) chkmin(f[i + 1][j], f[i][j] + max(0, sumo[j] - preo[p1[i + 1]]) + max(0, sumx[j] - prex[p1[i + 1]]));
if (j < n2 && (cur || s2[j + 1] == 'o')) chkmin(f[i][j + 1], f[i][j] + max(0, sum1[i] - pre1[p2[j + 1]]) + max(0, sum2[i] - pre2[p2[j + 1]]));
}
if (s1[i + 1] == '(') ++cur; else --cur;
}
printf("%d", ans + f[n1][n2]);
return 0;
}