题解 P8227 【「Wdoi-5」建立与摧毁的结界】

· · 题解

题解

为了方便起见，

考虑将一个形如 \verb!(!A\verb!)! 的括号序列（其中 A 为合法的括号序列），现在想要将它展开。那么唯一的路径就是堆叠 A，然后使用操作 1 展开 \verb!(!A\verb!)!。同样地，要试图堆叠一个序列 \verb!(!A\verb!)!，那只能把 A 堆叠。这是本题的一个基本思路。

要想直接实现 A 到 B 的转换有些麻烦。考虑先做性质 \text{A}。

设 f(l,r) 表示将合法括号序列 A[l:r] 展开需要的最少步骤数目，g(l,r) 表示将合法括号序列 A[l:r] 堆叠需要的最少步骤数目。

\texttt{(\textcolor{red}{(...)}\textcolor{cyan}{(...)}...\textcolor{orange}{(...)})}

需要分别展开 A[l+1:r-1] 当中的这些彩色区间，然后将 A[l+1:r-1] 使用操作 2 嵌套。此时能够发现 A[l:r] 已经变成了嵌套序列。

具体实现时，我们需要求出与一个括号相匹配的另外一个括号的位置。这一步骤可以进行预处理。具体而言，开一个栈，依次枚举。如果是左括号则直接入栈，如果是右括号则将它与栈顶的左括号匹配并将其弹出。容易发现这么做可以在 \mathcal O(n) 复杂度内预处理。

接着是考虑这两个「区间」\text{dp}。它可以使用递归来实现。我们需要用刚刚预处理好的匹配信息，进行次一级括号（上文当中的彩色括号。注意：次一级括号不包含这彩色括号内部的括号）的枚举。容易发现每对括号只会被枚举恰好一次，因此时间复杂度仍然是 \mathcal O(n)。

在此基础上，我们需要将括号序列 A 转换为 B，并输出将 A 转换为 B 所需最少步骤。

值得注意的是，如果可以将一个括号序列 S 经过一系列操作变为括号序列 T，那么总是可以按照反方向将 T 转化为 S，因为操作 1 和 2 是互逆的（对于一种操作，可以使用另一种操作撤回它的效果）。那么就能够发现，如果我们能把 B 用最少步骤展开为平铺括号序列，就能用这么多步骤把一个平铺括号序列转换为 B。

但这不是最小方案。考虑如何操作最小。举出下面这个情形：

\begin{aligned} &\texttt{\textcolor{red}{(...)}(..)(...)(.)\textcolor{blue}{(.....)}\textcolor{orange}{(..)}} \cr &\texttt{\textcolor{red}{(...)}(.....)(...)\textcolor{blue}{(.....)}\textcolor{orange}{(..)}} \end{aligned}

容易发现，如果存在某两个括号序列在 A,B 中的位置对应相等（图中的红色、蓝色、橘色括号序列。这里对应相等仅仅指次一级的括号位置相同，不包括这次一级括号里面的内容），那么它们就不需要展开到底，只需要对其中的部分进行递归操作即可。剩下来的部分（黑色部分）则需要全部展开。

这是与刚刚的区间 \text{dp} 相类似的。记 \operatorname{calc}(l,r) 表示将 A[l:r] 转换为 B[l:r] 的最少步骤数。那么我们需要枚举出所有的可以对应相等的次一级括号，对它们采取递归；剩下来的所有括号都必须得完全展开（不然就没办法进行转换了）。容易发现时间复杂度还是 \mathcal O(n) 的。

因此发现，总复杂度为 \mathcal O(n)。可以通过本题。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN =1e6+3;
int n; char A[MAXN],B[MAXN]; int P[MAXN],Q[MAXN];
void pre(char X[],int U[]){
    stack <int> S; up(1,n,i){
        if(X[i]==')') U[i]=S.top(),U[U[i]]=i,S.pop();
        else S.push(i);
    }
}
int  fun(int U[],int l,int r,bool f){ //0 推平
    if(r-1==l) return 0;
    if(U[r-1]==l+1){
        if(!f) return fun(U,l+1,r-1,true)+1;
        else   return fun(U,l+1,r-1,true); 
    }
    else{
        int ret=0; for(int p=l+1;p!=r;p=U[p]+1)
            ret+=fun(U,p,U[p],false);
        return ret+(f?1:2);
    }
}
bool L[MAXN],R[MAXN];
int  clc(int l,int r){
    if(r-1==l) return 0; int ret=0;
    for(int p=l;p!=r+1;L[p]=1,p=P[p]+1);
    for(int p=l;p!=r+1;R[p]=1,p=Q[p]+1);
    for(int p=l;p!=r+1;L[p]=1,p=P[p]+1)
        if(R[p]&&P[p]==Q[p] ) ret+=clc(p+1,P[p]-1);
    for(int p=l;p!=r+1;p=P[p]+1)
        if(P[p]!=Q[p]||!R[p]) ret+=fun(P,p,P[p],0);
    for(int p=l;p!=r+1;p=Q[p]+1)
        if(P[p]!=Q[p]||!L[p]) ret+=fun(Q,p,Q[p],0);
    for(int p=l;p!=r+1;L[p]=0,p=P[p]+1);
    for(int p=l;p!=r+1;R[p]=0,p=Q[p]+1);
    return ret;
}
int main(){
    scanf("%d%s%s",&n,A+1,B+1);
    pre(A,P),pre(B,Q);
    printf("%d\n",clc(1,n));
    return 0;

}