题解：AT_agc054_d [AGC054D] (ox)

· · 题解

[AGC054D] (ox)

题意

给定一个串 S 包含 (, ), o, x。

求最小的交换次数使得交换后的串将 o 替换为 ()， x 替换为 )( 后，是一个合法括号序列。

分析

看到“交换相邻两项的最小交换次数”，可以想到答案为：将原序列排成一个合法的序列，在此意义下的逆序对数。

不难发现，同样的字符会保留相同的顺序（考虑交换的过程，我们花费代价交换两个相同的元素显然不优）。

这样，我们就可以发现最终的序列是：提取出 (,),o,x 四个序列，按照一定顺序归并得到的序列。

我们此时可以得到该问题的多项式复杂度做法：使用 dp 记录四个序列各自选了多少个，每次加入的时候统计逆序对的变化。

观察数据范围，我们需要 O(n^2) 的算法。

再结合“归并操作有结合律”这个性质，我们可以猜到是要执行三次归并，每次归并两个数组。归并仍然使用上面的 dp 描述。

可以想到，先归并 ( 和 )，o 和 x，最后再进行一次归并得到答案。

我们发现 o 不会对括号串有任何影响，所以它和任意东西归并都应该保持其原来的顺序。

考虑 ( 和 ) 是怎样归并的：将最终的括号串中提取 ( 和 )，则其仍然构成括号串：

（只保留红色，依次拼接起来仍然是括号串）

所以我们大胆猜测 ( 和 ) 的归并为：进行最少步数的交换使得其为合法括号串。

这里我们可以不跑那个算法，可以考虑这样一个贪心：

仔细想想确实是对的，因为 x 只是要求当前栈中有元素，如果我们花费额外代价将 )( 变为 ()，至多只能使得其与 x 合并时减少一个逆序对，并不能使得答案更优。

于是我们就解决了这个问题。

代码：


const int maxn=8005;

pair<char,int> a1[maxn],a2[maxn];
int tot1,tot2;

void adjust(vector<pair<char,int>> v){
    int cnt=0;
    rep(i,0,v.size()-1){
        if(v[i].x=='(') cnt++;
        else{
            if(!cnt){
                cnt++;
                auto it=find_if(v.begin()+i,v.end(),lambda(auto x){return x.x=='(';});
                rotate(v.begin()+i,it,it+1);
            }
            else cnt--;
        }
    }
    for(auto i:v) a1[++tot1]=i;
}

int n;
int le1[maxn][maxn],le2[maxn][maxn];
int dp[maxn][maxn],stk[maxn][maxn];

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    memset(dp,0x3f,sizeof dp);
    string s;
    cin>>s;
    vector<pair<char,int>> v;
    rep(i,0,s.size()-1){
        if(s[i]=='x'||s[i]=='o') a2[++tot2]={s[i],i+1};
        else v.pb({s[i],i+1});
    }
    adjust(v);
    rep(i,1,tot1) rep(j,1,s.size()) le1[i][j]=le1[i-1][j]+(a1[i].y<=j);
    rep(i,1,tot2) rep(j,1,s.size()) le2[i][j]=le2[i-1][j]+(a2[i].y<=j);
    dp[0][0]=0;
    rep(i,0,tot1) rep(j,0,tot2){
        if(a1[i+1].x=='(') stk[i+1][j]=stk[i][j]+1,ckmin(dp[i+1][j],dp[i][j]+i+j-le1[i][a1[i+1].y]-le2[j][a1[i+1].y]);
        else if(stk[i][j]) stk[i+1][j]=stk[i][j]-1,ckmin(dp[i+1][j],dp[i][j]+i+j-le1[i][a1[i+1].y]-le2[j][a1[i+1].y]);

        if(a2[j+1].x=='o') stk[i][j+1]=stk[i][j],ckmin(dp[i][j+1],dp[i][j]+i+j-le1[i][a2[j+1].y]-le2[j][a2[j+1].y]);
        else if(stk[i][j]) stk[i][j+1]=stk[i][j],ckmin(dp[i][j+1],dp[i][j]+i+j-le1[i][a2[j+1].y]-le2[j][a2[j+1].y]);
    }
    cout<<dp[tot1][tot2]<<endl;
}