ARC175B 题解

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