背景:
这题是个裸的斜率优化+wqs二分(如果您没做过的话)。
按照我习惯的写法,当最优情况所取的区间个数不小于 m 时更新答案,但是这就会WA90。。。
后来神仙同学(zky)说了他的写法,不大于 m 时更新答案,于是我就AC了。
接着我翻了题解(第三篇),是在最优情况所取的区间个数不小于 m 时更新答案的。。。
然后我整个人就懵逼了。
接着我尝试取改第三篇题解(这种情况应该不会棕吧),发现是斜率优化时候那两个等于号的问题(2个while里面的,code在最底下)
我怀疑我学了个假的斜率优化。。。
现在,我总共有2个问题:
-
wqs二分如何判断在不大于m时更新答案或者在不小于m时更新答案?(我曾经看过一篇博客,说是在“最优解相同”时更新答案,然而我并不会构造)
-
斜率优化到底带不带等号啊?如果非带等号不可,如果double精损了怎么办(直接乘会炸long long)?
q[H=T=1]=0;
for(int i=1;i<=n;++i) {
while(H<T&&slope(q[H],q[H+1])<=2*s[i])++H;
int j=q[H];cnt[i]=cnt[j]+1,dp[i]=dp[j]+val(j+1,i)+x;
while(H<T&&slope(q[T-1],q[T])>=slope(q[T],i))--T;
q[++T]=i;
}
ANS=dp[n];return cnt[n];
谢谢路过
能帮忙最好(
禁止无意义回复