P2612

一道插入 DP 题。 分析 这一类型的 DP 大多是对许多段的维护，各个段之间的要求较弱或没有，一般都很难搞。 先把概率转成计数。 观察题面，我们可以考虑维护一条从上到下类似扫描线的东西，每次计算下移一格的贡献。很明显，在坐标轴上画出图像，应当由数个峰组成。从上往下扫描就会形成一些联续段，考虑 DP ......