新人求助，WA一个点很难受

背景：

这题是个裸的斜率优化+wqs二分（如果您没做过的话）。

按照我习惯的写法，当最优情况所取的区间个数不小于

m

时更新答案，但是这就会WA90。。。

后来神仙同学(zky)说了他的写法，不大于

m

时更新答案，于是我就AC了。

接着我翻了题解（第三篇），是在最优情况所取的区间个数不小于

m

时更新答案的。。。

然后我整个人就懵逼了。

接着我尝试取改第三篇题解（这种情况应该不会棕吧），发现是斜率优化时候那两个等于号的问题（2个while里面的,code在最底下）

我怀疑我学了个假的斜率优化。。。

现在，我总共有2个问题：

wqs二分如何判断在不大于m时更新答案或者在不小于m时更新答案？（我曾经看过一篇博客，说是在“最优解相同”时更新答案，然而我并不会构造）
斜率优化到底带不带等号啊？如果非带等号不可，如果double精损了怎么办（直接乘会炸long long）？

CPP

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];

谢谢路过

能帮忙最好（

禁止无意义回复

新人求助，WA一个点很难受

讨论操作

回复

相关推荐

新人求助，WA一个点很难受