这个题不是很难,算是范德蒙恒等式的应用
假如说这个题目没有问号限制;我们通过一个点把这个链分成两部分
那么从这个点断开的最优方案就是这个点左侧的‘(’和右侧的‘)’取min
O(n)预处理然后直接再扫一边就可以了
但这个题目是有括号限制的,那么如果再加上问号的话,只需要枚举左边的‘?’有多少个变成了‘(’,相应的右边的变化情况
假设断点左边的‘(’为a,右边的‘)’为b,左边的’?‘为c,右边的’?‘为d
那么很显然的一个dp方程
$ans_{p}=\sum_{i=0}^{c}(a+i) C_{c}^{i} C_{d}^{a+i-b}$
=$\sum_{i=0}^{c}aC_{c}^{i}C_{d}^{a+i-b}+\sum_{i=0}^{c}iC_{c}^{i}C_{d}^{a+i-b}$
直接范得蒙恒等式带走了
$ans_{p}=aC_{c+d}^{d-a+b}+cC_{c+d-1}^{d-a+b-1}$