Larry76 牛牛 
首先考虑没有 ox 怎么做，就是将括号序列调成合法。\(|S|\) 不大直接模拟一遍，记录 \(now\) 表示一个前缀权值，当遇到一个 ( 时 \(+1\)，遇到一个 ) 时 \(-1\)，当 \(now < 0\) 的时候说明序列不合法即 ) 多了，暴力向后找到第一个 ( 交换到当前的 ) 前面。这样我们迫不得已时才移动，能够证明得出来的最终括号序列是惟一的。
考虑加入 ox 会造成什么影响。我们先忽略移动 ox 所带来的的影响，假设没有中间间隔的 ox，提出所有的左右括号然后按照上面的方式得到一个合法的括号序列，记这个步数为 rop。注意到我们这样移动即使中间隔着 ox，也不会造成初始 ox 顺序的改变。接下来加入 ox，把先前忽略掉的步数补回来。设 \(f_{i,j}\) 表示当前填入了 \(i\) 个括号和 \(j\) 个 ox，可以发现这个的交换次数贡献为括号和 ox 在原序列上位置的逆序对个数，直接枚举当前填入什么东西。需要特别注意的是记最终括号序列的前缀权值和为 pre，o 可以随意填，但是 x 不能放在两个合法的括号序列之间，即 \(pre_i = 0\) 的位置。
于是代码流程变得十分清晰了：先将左右括号和 ox 分别提出来，记录下它们的初始位置和总个数，设有 \(n\) 个左右括号和 \(m\) 个 ox；然后求纯括号序列的交换次数，并预处理出 pre 数组；最后进行 DP，补偿回算上 ox 的交换次数。最后的答案即为 \(f_{n,m} + rop\)。时间复杂度是 \(\mathcal O(|S|^2)\) 的。
#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) (__gcd(x,y))
#define lcm(x,y) (x*y/gcd(x,y))
#define lg(x,y) (__lg(x,y))
using namespace std;
namespace FastIO
{
template<typename T=int> inline T read()
{
T s=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s*w;
}
template<typename T> inline void read(T &s)
{
s=0; int w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
s=s*w;
}
template<typename T,typename... Args> inline void read(T &x,Args &...args)
{
read(x),read(args...);
}
template<typename T> inline void write(T x,char ch)
{
if(x<0) x=-x,putchar('-');
static char stk[25]; int top=0;
do {stk[top++]=x%10+'0',x/=10;} while(x);
while(top) putchar(stk[--top]);
putchar(ch);
return;
}
}
using namespace FastIO;
namespace MTool
{
static const int Mod=998244353;
template<typename T> inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
template<typename T> inline void cmax(T &a,T b) {a=a>b?a:b;}
template<typename T> inline void cmin(T &a,T b) {a=a<b?a:b;}
template<typename T> inline void Madd(T &a,T b) {a=a+b>Mod?a+b-Mod:a+b;}
template<typename T> inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
template<typename T> inline void Mmul(T &a,T b) {a=a*b%Mod;}
template<typename T> inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
template<typename T> inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
template<typename T> inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
template<typename T> inline T Cmul(T a,T b) {return a*b%Mod;}
template<typename T> inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
inline int qpow(int a,int b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
inline int qmul(int a,int b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
inline int Qpow(int a,int b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
}
using namespace MTool;
inline void file()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
return;
}
bool Mbe;
namespace LgxTpre
{
static const int MAX=8010;
static const int inf=2147483647;
static const int INF=4557430888798830399;
static const int mod=1e9+7;
static const int bas=131;
char s[MAX];
int n,a[MAX],num,rop,pre[MAX];
int bck[MAX],cnt,box[MAX],con;
int f[MAX][MAX],sub1[MAX],sub2[MAX];
inline void mian()
{
scanf("%s",s+1); n=strlen(s+1);
for(int i=1;i<=n;++i)
if(s[i]=='('||s[i]==')') bck[++cnt]=i,a[cnt]=(s[i]=='(')?1:-1;
else box[++con]=i;
for(int now=1;now<=cnt;++now)
{
if(a[now]&&!num)
{
int to=now;
while(a[to]!=1) ++to;
rop+=to-now;
while(to>now) Swp(bck[to],bck[to-1]),Swp(a[to],a[to-1]),--to;
}
num+=a[now],pre[now]=num;
}
memset(f,0x3f,sizeof f),f[0][0]=0;
for(int i=0;i<=cnt;++i) for(int j=0;j<=con;++j)
{
if(i!=cnt&&j) sub1[i]+=box[j]>bck[i+1];
if(i!=cnt) cmin(f[i+1][j],f[i][j]+sub1[i]);
if(j!=con&&i) sub2[j]+=bck[i]>box[j+1];
if(j!=con&&(pre[i]>0||s[box[j+1]]=='o')) cmin(f[i][j+1],f[i][j]+sub2[j]);
}
write(f[cnt][con]+rop,'\n');
return;
}
}
bool Med;
signed main()
{
// file();
fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
int Tbe=clock();
LgxTpre::mian();
int Ted=clock();
cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
return (0-0);
}