10.24
P5658 [CSP-S2019] 括号树
这个实际上就是给定一个括号序列\(a\)，然后对于每一个\(i\)，来说，求出\([1,i]\)的所有合法括号子串（发现这个其实只需要求以\(i\)为结尾的合法括号后缀然后做前缀和就行了）那么只需要找出以\(i\)为结尾最短合法括号后缀就行，（设最短长度为\(g_i\),总数为\(f_i\)(设最短的位置在\(j\))），因为所有合法后缀一定是以\(j-1\)结尾的合法后缀再拼接\([j,i]\)就行。（当然包括\([j,i]\))所以\(f_i=f_j+1\))，所以，问题又成了求以\(i\)结尾的最短合法括号序列了。这个用\(g_i\)更新好了，挺好想的，然后没了。