题意
做法
结论:对于字符串\(s\),其为合法括号序列的充要条件为
(1)\(|s|\)为偶数,
(2)构造序列\(a_i\),若\(s_i\)='(' or '?',则\(a_i=+1\);若\(s_i\)=')',则\(a_i=-1\),\({a_i}\)的前缀和均\(\ge 0\)
(3)构造序列\(b_i\),若\(s_i=\)')' or '?',则\(b_i=+1\);若\(s_i\)='(',则\(b_i=-1\),\({b_i}\)的后缀和均\(\ge 0\)
证明显然
令\(sa_i,sb_i\)分别为\(\{a\},\{b\}\)的前缀和、后缀和。
推论:\(s_{l,r}\)为合法括号序列的充要条件为
(1)\(r-l+1\)为偶数
(2)\(\forall i\in[l,r]\),\(sa_{l-1}\le sa_i\)
(3)\(\forall i\in[l,r]\),\(sb_{r+1}\le sa_i\)
令\(nxt_i=\min\{x|x>i \and sa_x<sa_i\}\),\(pre_i=\max\{x|x<i \and sb_x<sb_i\}\)
推论(2)(3)可改写为,\(r< nxt_{l-1}\)、\(l> pre_{r+1}\)
令\(f_i\)为前\(s[1:i]\)的最大价值,转移是一个经典的二维偏序问题
标签:gym104531,le,forall,ge,Bracket,序列,sa From: https://www.cnblogs.com/Grice/p/17703801.html