前言
因为本人尚菜，所以本篇文章没有什么数学符号，请大家放心食用。
题目分析
先吐槽一嘴，这个 o 表示 ()，这个 x 表示 )(，十分形象。
好，我们先观察原序列，容易得出第一条性质：
ox的加入不会让我们不合法的序列变合法，相反，它会让我们合法的序列变不合法。
于是可以得出，无论如何，只要我们想要得到合法的序列，我们肯定都要先将去除 ox 的括号序列变得合法。
那么惯性的思考下去，也就是我们可以将贡献拆开算，分别是忽略 ox 后的括号序列变合法的最小步数和 ox 步数的平衡。
这个时候可能会晕的一点是，为什么可以这么拆，或者说，为什么计算最小步数的时候可以忽略中间的 ox。其实，我们并没有忽略掉我们的 ox，只不过我们运用了两个视角来计算同一件事请而已，我们先忽略 ox 从纯括号中观察得到纯括号序列的移动步数，然后再从 ox 的角度观察序列的变化。此时不但得出，对于 ox 来说，我们的变化就是原序列经过变换后的逆序对数。
然后最后一步进行 dp 就是比较朴素的，设 \(dp_{i,j}\) 为已经观察了 \(i\) 个括号和 \(j\) 个序列后，我们观察出的最小步数。
然后需要特殊考虑一下 x 的位置，不难看出，x 只能在 ( 的后面。所以转移的时候需要特判。
代码实现
这里只给出了代码的关键部分，其余部分还恳请读者自行实现。
char s[MAX_SIZE];
int posb[MAX_SIZE];
int bl[MAX_SIZE];
int posv[MAX_SIZE];
int presum[MAX_SIZE];
int n, m, k;
int dp[MAX_SIZE][MAX_SIZE];
int t1[MAX_SIZE];
int t2[MAX_SIZE];
void main() {
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++){
if(s[i] == '('){
posb[++m] = i;
bl[m] = 0;
} else if(s[i] == ')'){
posb[++m] = i;
bl[m] = 1;
} else {
posv[++k] = i;
}
}
int now = 0;
int ans1 = 0;
for(int i=1;i<=m;i++){
if(bl[i] && !now){
int j=i;
while(bl[j]){
++j;
}
ans1 += j-i;
while(j>i){
swap(bl[j],bl[j-1]);
swap(posb[j],posb[j-1]);
--j;
}
}
now += (bl[i] ? -1 : 1);
presum[i] = now;
}
memset(dp,0x7f,sizeof(dp));
dp[0][0] = 0;
for(int i=0;i<=m;i++){
for(int j=0;j<=k;j++){
if(i<m){
if(j){
t1[i] += (posv[j] > posb[i+1]);
}
dp[i+1][j] = min(dp[i+1][j],dp[i][j] + t1[i]);
}
if(j<k){
if(i){
t2[j] += (posb[i] > posv[j+1]);
}
if(presum[i]>0 || s[posv[j+1]]=='o'){
dp[i][j+1] = min(dp[i][j+1],dp[i][j] + t2[j]);
}
}
}
}
printf("%lld\n",dp[m][k]+ans1);
return void();
}