AcWing 1070. 括号配对-逆沧澜
原题链接
中等
作者:
xyd
,
2023-02-06 10:10:33
,
所有人可见
,
阅读 140
这样可以不用区间DP,代码短,思考量差不多,记得分好情况,成不成在于初始化
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int f[N][N];
char s[N];
bool match(int l,int r)
{
if(s[l]=='('&&s[r]==')') return true;
if(s[l]=='['&&s[r]==']') return true;
return false;
}
int main(){
scanf("%s",s+1);
int n=strlen(s+1);
for(int l=n;l>0;l--)
for(int r=l;r<=n;r++)
if(l==r) f[l][r]=1;
else
{
f[l][r] = 0x3f3f3f3f;//若果没有这句话,会错的连喳喳都不剩
if(match(l,r)) if(r==l+1) f[l][r]=0;
else f[l][r]=f[l+1][r-1];
else f[l][r]=min(f[l][r],min(f[l+1][r],f[l][r-1])+1);
for(int k=l;k<r;k++) f[l][r]=min(f[l][k]+f[k+1][r],f[l][r]);
}
printf("%d",f[1][n]);
}