- 题解
D1T4 括号匹配 dp写法
- @ 2024-10-2 17:02:15
#include <bits/stdc++.h>
using namespace std;
int n,a,b;
string s;
int pi[1005];
int dp[1005][1005][3][3];
void solve()
{
cin>>n>>a>>b>>s;
s=" "+s;
//处理对应()的位置
stack<int>st;
for(int i=1;i<=n;i++)
{
if(s[i]=='(')st.push(i);
else
{
pi[i]=st.top();
pi[st.top()]=i;
st.pop();
}
}
for(int len=2;len<=n;len+=2)
{
for(int l=1,r=len;r<=n;l++,r++)
{
if(s[l]==')' || s[r]=='(')continue;
if(pi[l]==r)//匹配
{
if(len==2)// ()
{
dp[l][r][0][0]=0;
dp[l][r][1][1]=a;
dp[l][r][2][2]=b;
}else if(pi[l+1]==r-1)// (()) 内部匹配
{
dp[l][r][0][0]=0+max(dp[l+1][r-1][1][1],dp[l+1][r-1][2][2]);
dp[l][r][1][1]=a+max(dp[l+1][r-1][0][0],dp[l+1][r-1][2][2]);
dp[l][r][2][2]=b+max(dp[l+1][r-1][0][0],dp[l+1][r-1][1][1]);
}else // (()()) (()(())) (()()()) 内部不匹配
{
for(int i=0;i<=2;i++)
{
for(int j=0;j<=2;j++)
{
if(i!=0&&j!=0)dp[l][r][0][0]=max(dp[l][r][0][0],dp[l+1][r-1][i][j]);
if(i!=1&&j!=1)dp[l][r][1][1]=max(dp[l][r][1][1],dp[l+1][r-1][i][j]);
if(i!=2&&j!=2)dp[l][r][2][2]=max(dp[l][r][2][2],dp[l+1][r-1][i][j]);
}
}
dp[l][r][0][0]+=0;
dp[l][r][1][1]+=a;
dp[l][r][2][2]+=b;
}
}else //不匹配 ()() ()(())
{
if(pi[l]==pi[r]-1)
{
for(int i=0;i<=2;i++)
{
for(int j=0;j<=2;j++)
{
if(i==j)continue;
dp[l][r][i][j]=dp[l][pi[l]][i][i]+dp[pi[r]][r][j][j];
}
}
}else // ()()()()
{
for(int i=0;i<=2;i++)
{
for(int j=0;j<=2;j++)
{
for(int t1=0;t1<=2;t1++)
{
if(t1==i)continue;
dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][pi[l]][i][i]+dp[pi[l]+1][r][t1][j]);
}
}
}
}
}
}
}
int mx=0;
for(int i=0;i<=2;i++)
{
for(int j=0;j<=2;j++)
{
mx=max(mx,dp[1][n][i][j]);
}
}
cout<<mx;
}
int main()
{
freopen("bracket.in", "r", stdin);
freopen("bracket.out", "w", stdout);
solve();
return 0;
}
0 条评论
目前还没有评论...