CF1264D2 Beautiful Bracket Sequence

这个题不是很难,算是范德蒙恒等式的应用

假如说这个题目没有问号限制;我们通过一个点把这个链分成两部分

那么从这个点断开的最优方案就是这个点左侧的‘(’和右侧的‘)’取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}$

上一篇:【Java-笔试面试】接口和抽象类的区别?


下一篇:【无标题】