本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-25 08:42:00

题意

给出一个括号序列，有两种操作方式，交换两个字符需要 $A$ 的代价，直接修改一个字符需要 $B$ 的代价，求使这个序列合法需要的最小代价。

思路

这题看上去好像是dp，但是复杂度显然不太对。

我们发现，交换相当于两次修改；而若把一个左括号改成右括号，再把一个右括号改成左括号，就相当于把这两个字符交换。

这样就可以先无脑修改，记录下修改为左括号和右括号的次数，最后再处理一下可以转换成交换操作的数量即可。

因此从左到右操作，若碰到左括号则压入栈中；碰到右括号时，若栈中有左括号则弹出一个与之匹配，若没有则只能修改成左括号并压入栈中，同时记录一下修改为左括号的次数。

最后若栈中还剩 $k$ 个左括号，显然此时 $k$ 一定为偶数。那么需要把其中 $\frac{k}{2}$ 个改成右括号以令其匹配，那么 $\frac{k}{2}$ 就是修改为右括号的次数。

此处由于只有左括号会被压入栈中，所以不需要开栈存储，只需要记录一下栈中的左括号数量即可。

最后可以把两种修改各一次转换为交换，贪心求出答案即可。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=1e6+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int n,a,b,sl,sr,sn;\/\/sl sr为修改为左\/右括号的次数，sn为栈中的左括号数量 
char s[N];
signed main()
{
	n=read(),a=read(),b=read();
	cin>>s;
	for(int i=0;i<2*n;i++)
	{
		if(s[i]==')')
		{
			if(sn) sn--;
			else sl++,sn++;
		}
		else sn++;
	}\/\/如上述，记录修改为左括号次数 
	if(sn) sr=sn\/2;\/\/计算修改为右括号次数 
	if(sl<sr) swap(sl,sr);\/\/使sl为较大值 
	if(b*2<=a) cout<<(sl+sr)*b;\/\/若两次修改代价小于交换，则全用修改 
	else cout<<sr*a+(sl-sr)*b;\/\/否则把能转换的修改全部转换 
	return 0;
}