hdoj3698 Let the light guide us——线段树优化dp

终于ac了,好久不写线段树,成段更新变生疏了。
第一道用线段树优化的dp题。线段树用于成段更新,求区间最小值(包括历史值在内的最小值)。
dp[i][j]:前i行,且第i行选第j个可以得到的最小花费
dp[i][j]=min{dp[i-1][k]|1<=k<=m且abs(j-k)<=f[i-1][k]+f[i][j]}+cost[i][j]
复杂度n*m*m,超时
其实对于确定的i,j可以选择哪些k呢?abs(j-k)<=f[i][j]+f[i-1][k]等价于以j为中心,f[i][j]为半径的区间和以k为中心,f[i-1][k]为半径的区间的重合部分,so。。求解每个阶段的时候,可以建立线段树[1,m],然后不断加入上个阶段的dp值,dp[i-1][k]的区间是
[max(1,k-f[i-1][k]),min(m,k+f[i-1][k])],线段树维护最小值,注意lazy字段,lazy表示要往下更新的最小值,但是子孙节点的lazy有可能是小于它的(加入先对父区间更新为10,然后左子区间更新为8,这时候子区间的lazy就要比父区间小了),所以pushdown的时候,只有儿子节点的lazy没值或者小于父节点的lazy,才能重写这个儿子节点的lazy,否则可能导致结果偏大