设$f[i]$表示以$i$结尾(必须包括$i$)的最长的美观的子段的长度
有
- $i$与$i-1-f[i-1]$不匹配
$$f[i] = 0$$
- $i$与$i-1-f[i-1]$匹配
$$f[i] = f[i-1]+2+f[i-1-f[i-1]-1]$$
代码
#include <iostream>
#include <cstring>
typedef long long ll;
using namespace std;
const int N = 1e5+7;
int n,ans,f[N];
char s[N];
int main() {
scanf("%s",s+1); n = strlen(s+1);
f[1] = 0;
for(int i = 2;i <= n; ++i) {
if(s[i] == '(' || s[i] == '[' || s[i] == '{') continue;
if((s[i-1-f[i-1]] == '(' && s[i] == ')') || (s[i-1-f[i-1]] == '[' && s[i] == ']') || (s[i-1-f[i-1]] == '{' && s[i] == '}')) {
f[i] = f[i-1]+2+(i-2-f[i-1]? f[i-2-f[i-1]]:0);
ans = max(ans,f[i]);
}
}
cout << ans;
return 0;
}
Orz
为…为什么要DP……
Orz
// dp[i]表示以第i个元素结尾的连续合法字符串的最长的长度
// 像这种’连续的’, 转移大多和上一个有关
非常棒赞赞赞赞