以下为核心代码:
const int N = 100010;
stack <int> in;
int f [N];
char s [N];
inline bool match ( int i, int j ){
if ( s [i] == '(' && s [j] == ')' ) return true;
if ( s [i] == '[' && s [j] == ']' ) return true;
if ( s [i] == '{' && s [j] == '}' ) return true;
return false;
}
int main (){
scanf ( "%s", s+1 );
for ( int i = 1; i <= (int)strlen(s+1); ++i ){
if ( in.size() && match (in.top(),i) ){
f [i] = f [in.top()]+2 + f [i-1];
if ( i-f[i]>=1 ) f [i] += f [ i-f[i] ];
in.pop();
}else
in.push (i);
}
int ans = 0;
for ( int i = 1; i <= (int)strlen(s+1); ++i ) ans = max ( ans, f [i] );
printf ( "%d", ans ); return 0;
}
初始状态为f[i]=0任取1<=i<=n
目标状态为MAX{f[i]任取1<=i<=n}
以结尾的位置为阶段,以f[i]
即 以i结尾的“完美括号序列”的最大长度为状态,时刻维护位置i之前的f[i]
的正确
思考后容易得出转移方程(见代码)
请读者思考为何将if下第一行替换为以下写法也是正确的(答案在题解最下方)
f [i] = 2 + f [i-1];
思考题答案:以左括号位置结尾的“完美括号序列”的最大长度总是0