@[AThousandSuns](/user/72118)
by Rain_chr @ 2024-01-03 15:22:30
以及同样写法的题解作者：
@[Fading](/user/20309)
by Rain_chr @ 2024-01-03 15:23:46
对不起啊，刚刚又尝试了一下，之前那种写法也是对的。
但问题是，第二种写法为什么不合法的i不会把合法的队尾踢走，看上去dp和代价都是没有单调性的啊
by Rain_chr @ 2024-01-03 15:40:28
我天哪怎么还有问题……这让我这退役老人很难办（x
我刚毛估估了一下似乎至少这题里面，这个单调性还是满足的应该是不会出现非法更新的情况……不过应该还是上面的写法更好吧……当然可能我胡的有误（（
by AThousandSuns @ 2024-01-03 22:35:36
@[AThousandSuns](/user/72118) 我和我的同学拍了一下，会有不合法的情况，但非常离奇的是，不合法的情况不会入队……
by Rain_chr @ 2024-01-18 14:45:46
话说我第一眼看成刚毛，脑子马上就反应疣足，再就是辅助肌肉运动，这还有救吗……
by Rain_chr @ 2024-01-18 14:47:40
@[Rain_chr](/user/684254) 后来和同学讨论了一下。
设i为当前的点,j为q.back(),lt[j]为j的转移区间左端点并且有 $j<lt[j]<i$。
可以发现，j 就是 i 的最优转移点，因为队列中的转移区间两两无交，也就是 i 的代价一定是由 j 转移过来的。
故i->lt[j]的代价是
$dp[j]+(S_i-S_j+i-j-1-L)^p+(S_{lt[j]}-S_i+i-lt[j]-1-L)^p$
j->lt[j]的代价是
$dp[j]+(S_lt-S_{j}+lt-j-1-L)^p$
by Rain_chr @ 2024-01-18 14:59:47
作差得
$(S_i-S_j+i-j-1-L)^p+(S_{lt[j]}-S_i+i-lt[j]-1-L)^p-(S_{lt}-S_{j}+lt-j-1-L)^p$
现在就是要说明这个东西>=0
by Rain_chr @ 2024-01-18 15:01:13
式子搞反了，是 lt[j]-i
by Rain_chr @ 2024-01-18 15:03:20
@[Rain_chr](/user/684254) 尊强啊，我一直很疑惑为什么可以直接写不判边界，自己写的时候就加上边界了，发现没错就没管
by XOOR @ 2024-05-15 16:43:00