网站首页
编程语言
数据库
系统相关
其他分享
编程问答
bzoj4350
2024-07-08
[BZOJ4350] 括号序列再战猪猪侠 题解
我们设\(dp_{i,j}\)表示第\(i\)到第\(j\)个括号合并为序列且最外层不是括号\(i\)的可能性,\(f_{i,j}\)表示最外层是括号\(i\)的可能性。则有:\[\begin{cases}dp_{i,j}=\sumf_{i,k}(dp_{k+1,j}+f_{k+1,j})\\f_{i,j}=dp_{i+1,j}+f_{i+1,j}\end{cases}\]当然,并不是所