【BZOJ1911】【APIO2010】特别行动队

已经有感觉了诶。。一眼秒出是斜率优化

因为修正战斗力是个二次函数并且开口向下,显然如果对于一个点x而言,l<r且r优于l,因为x是单调递增的,那么d[x]-d[r]和d[x]-d[l]都是单调递增。(显然)就有决策单调性了嘛。

先算出前缀和d,那么r优于l的条件是(在a决策的意思是把a+1到x合并):

$$\small{dp[r]+a(d[x]-d[r])^2+b(d[x]-d[r])>dp[l]+a(d[x]-d[l])^2+b(d[x]-d[l])}$$

$$\small{dp[r]-2a·d[x]d[r]+a·d[r]^2-b·d[r]>dp[l]-2a·d[x]d[l]+a·d[l]^2-b·d[l]}$$

$$2a·d[x]+b<\frac{(a·d[r]^2+dp[r])-(a·d[l]^2+dp[l])}{d[r]-d[l]}$$

就随意乱搞了

说点什么

您将是第一位评论人!

提醒
wpDiscuz