题解：AT_agc054_d [AGC054D] (ox)

· · 题解

思路

对于 o，因为要替换为 ()，不会对结果造成影响，这样可以将 o 看做占位符。对于 x，它必须放在 ( 的右边，因为它要变成 )(。这样我们可以记录下 (，) 和 o，x 的位置，然后首先开一个前缀和数组 pre，pre_i 表示从 1 到 i 的序列是否合法。如果 s_i=( 则 pre_i=pre_{i-1}+1，如果 s_i=) 则 pre_i=pre_{i-1}-1。如果 pre_i<0，证明 ) 多了，这时把右边最近的 ( 提过来，这一部分的步数设为 ans_1。然后我们处理 o 和 x，这一部分可以用二维 dp，dp_{i,j} 表示处理完前 i 个括号和前 j 个 o 和 x 所需的最小代价。得出最小步数 ans_2。最后 ans_1+ans_2 就是最小步数。

整个算法时间复杂度为 O(n^2)，可以通过本题。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=8009,INF=0x3f3f3f3f;
int n,cnt1,cnt2,a[N],b[N],pre[N],r1[N],r2[N],ans1,s1[N][N],s2[N][N],dp[N][N];
char s[N];
int main(){
    scanf("%s",s+1); 
    n=strlen(s+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='('||s[i]==')') a[++cnt1]=i;
        else b[++cnt2]=i;
    }
    for(int i=1;i<=cnt1;i++){
        pre[i]=pre[i-1]+(s[a[i]]=='('?1:-1); //前缀和
        if(pre[i]<0){
            for(int j=i+1;j<=cnt1;j++) if(s[a[j]]=='('){
                int t=a[j];
                for(int k=j;k>i;k--) a[k]=a[k-1];
                a[i]=t;
                ans1+=j-i; //把后面的右括号提前
                pre[i]+=2; //成功配对
                break;
            }
        }
    }
    for(int i=1;i<=cnt1;i++) 
        for(int j=1;j<=cnt2;j++){
            s1[i][j]=s1[i][j-1]+(a[i]<b[j]); //统计前 j 个 "o","x" 中有多少个位置在括号 a[i] 之前，用于计算将非括号字符插入到括号后的代价
            s2[i][j]=s2[i-1][j]+(b[j]<a[i]); //统计前 i 个 "o","x" 括号中有多少个位置在非括号字符（o,x） b[j] 之后，用于计算将括号插入到 "o","x" 后的代价
        }
    for(int i=0;i<=cnt1;i++) 
        for(int j=0;j<=cnt2;j++){
            if(!j) 
                continue;
            if(!i) 
                dp[i][j]=INF*(dp[i][j-1]||s[b[j]]=='x');  //不可行情况
            else{
                dp[i][j]=dp[i-1][j]+s1[i][j];
                if(pre[i]>0||s[b[j]]=='o') 
                    dp[i][j]=min(dp[i][j],dp[i][j-1]+s2[i][j]); //最小移动
            }
        }
    printf("%d\n",ans1+dp[cnt1][cnt2]);
    return 0;
}