网站首页
编程语言
数据库
系统相关
其他分享
编程问答
CF56E
2024-07-25
CF56E 题解
题面设骨牌\(i\)倒下之后会连带压倒\([i+1,r_i]\)的骨牌,那么有\(z_i=\max_{j=i+1}^{r_i}z_j+(j-i)\)考虑线段树优化dp,但是\((j-i)\)不好维护,所以套路地修改式子,得到:\(z_i+i=\max_{j=i+1}^{r_i}(z_j+j)\)所以线段树维护\(z_i+i\)的区间最大值即可,\(r_i\)可以二分求