[AGC054D] (ox)

题意

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

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

分析

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

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

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

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

观察数据范围，我们需要

O(n^2)

的算法。

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

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

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

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

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

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

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

当栈空了且遇到一个 ) 时，我们找到当前位置之后最靠前的一个 ( 换过来使其合法。

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

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

代码：

CPP


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

题解：AT_agc054_d [AGC054D] (ox)

文章操作

[AGC054D] (ox)

题意

分析

相关推荐

评论

题解：AT_agc054_d [AGC054D] (ox)