题解：【AGC054D】 (ox)

题目链接

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);
}