括号配对
题意
递归定义一组字符匹配模式
增加几个字符满足这个匹配。
思路
添加多少个字符，可以转化为n-“回文子串”，这里的回文子串需要重新定义
AAAABBBB：A符合定义，B也符合定义的话：最长子串，我们枚举中间端点取最大值。
ABBA：这种情况，我们判断【l， r】 match（l,r)是不是匹配，匹配的话f（l+1，r-1）+2
代码
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
#define mst(s,_s) memset(s, _s, sizeof(s))
const double PI
= acos(-1.0);
const double eps
= 1e-6;
const int INF
= 0x3f3f3f3f;
const int N
= 1e3+100;
int T
,n
,m
;
char str
[N
];
int f
[N
][N
];
bool match(char a
,char b
)
{
if(a
=='(' && b
==')') return true;
if(a
=='[' && b
==']') return true;
else return false;
}
int main() {
cin
>>str
+1;
n
=strlen(str
+1);
for(int len
=2;len
<=n
;len
++)
{
for(int l
=1;l
+len
-1<=n
;l
++)
{
int r
=l
+len
-1;
if(len
==1) f
[l
][r
]=0;
if(match(str
[l
],str
[r
])) f
[l
][r
]=max(f
[l
][r
],f
[l
+1][r
-1] + 2);
for(int k
=l
;k
<r
;k
++)
{
f
[l
][r
]=max(f
[l
][r
],f
[l
][k
]+f
[k
+1][r
]);
}
}
}
cout
<<n
- f
[1][n
]<<endl
;
return 0;
}
