萌新求助模板dp问题
  • 板块学术版
  • 楼主tommy0221
  • 当前回复19
  • 已保存回复19
  • 发布时间2020/7/28 18:55
  • 上次更新2023/11/6 21:56:32
查看原帖
萌新求助模板dp问题
123384
tommy0221楼主2020/7/28 18:55

斜率优化里面为啥不带等号会挂啊(2个while),调了好久发现是这个锅/kk

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

H=1,T=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;
    }
2020/7/28 18:55
加载中...