本文主要是介绍[loj#2868][线段树][笛卡尔树][DP]会议，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
传送门
题解
不想写了所以下面没有代码
看题解发现我第一步就自闭了…感觉我在这种题从来都不会想DP的事情…
设一个 f [ i ] [ j ] f[i][j] f[i][j]表示 [ i , j ] [i,j] [i,j]的答案是什么
如果我们找到了这个区间的最大值位置 p p p，那么显然要不你就是让人们全部走到最大值的左边，要不就是走到最大值的右边
那么转移就是
f [ i ] [ j ] = m i n ( f [ i ] [ p − 1 ] + h [ p ] ∗ ( r − p + 1 ) , f [ p + 1 ] [ j ] + h [ p ] ∗ ( p − i + 1 ) ) f[i][j]=min(f[i][p-1]+h[p]*(r-p+1),f[p+1][j]+h[p]*(p-i+1)) f[i][j]=min(f[i][p−1]+h[p]∗(r−p+1),f[p+1][j]+h[p]∗(p−i+1))
注意到转移与最大值相关，考虑笛卡尔树
又发现是类似笛卡尔树的分治结构，确认过眼神就是你了
搜笛卡尔树上的每个点，如果他在 [ L i , R i ] [L_i,R_i] [Li,Ri]是最大值，那么我们需要保存两种值
f [ L i , L i ] , f [ L i , L i + 1 ] , . . . , f [ L i , R i ] f[L_i,L_i],f[L_i,L_{i}+1],...,f[L_i,R_i] f[Li,Li],f[Li,Li+1],...,f[Li,Ri]以及
f [ R i , R i ] , f [ R i − 1 , R i ] , . . . , f [ L i , R i ] f[R_i,R_i],f[R_{i}-1,R_i],...,f[L_i,R_i] f[Ri,Ri],f[Ri−1,Ri],...,f[Li,Ri]
对于转移，以第一种值为例讨论
在 p p p左边的直接赋值了，仅讨论在右边的情况
那么就是 m i n ( f [ p + 1 ] [ u ] + ( p − i + 1 ) ∗ h [ p ] , f [ i ] [ p ] + ( u − p + 1 ) ∗ h [ p ] ) min(f[p+1][u]+(p-i+1)*h[p],f[i][p]+(u-p+1)*h[p]) min(f[p+1][u]+(p−i+1)∗h[p],f[i][p]+(u−p+1)∗h[p])
发现转移具有单调性，即第一种是一段，第二种又是一段
二分这个分界点
现在所需要的就是支持区间赋值为一个一次函数，区间增加一个值，以及单点查询
这个线段树即可
以后这种区间询问的题，不要老想一些数据结构什么的，其实DP也是可做的…
代码以后或许会补？？
这篇关于[loj#2868][线段树][笛卡尔树][DP]会议的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
