问问
查看原帖
问问
141599
sinsop90楼主2023/2/9 12:26

wqs二分里套斜率优化

有两种写法, 在斜率优化的转移和最后答案的处理上有区别

f[i] = f[Q[l]] +  m * (pre[i] - pre[Q[l]]) * (pre[i] - pre[Q[l]]) + x;

(f[n] - ans * m) - pre[n] * pre[n]

f[i] = f[Q[l]] + (pre[i] - pre[Q[l]]) * (pre[i] - pre[Q[l]]) + x;

m * (f[n] - ans * m) - pre[n] * pre[n]

第一种是错的(0分), 第二种是对的, 但是我觉得第一种应该也对才对啊..

在下面用 aia_i 代替 preipreQlpre_i - pre_{Q_l}

具体: 答案的式子是这样: (mai2)prenpren(m\sum {{a_i}^2}) - pre_n * pre_n

第一种在dp时求得 (mai2+x)=mai2+mx\sum (m{a_i}^2 + x) = m\sum{a_i}^2 + mx 所以最后减掉 mxmx

第二种在dp时求得 (ai2+x)=ai2+mx\sum({a_i}^2+x) = \sum{a_i}^2 + mx 所以最后剪掉mx后再乘上m

那为什么第一种是错的?

2023/2/9 12:26
加载中...