【BZOJ1096】【ZJOI2007】仓库建设

居然又是斜率优化。。

总结出一些规律:凡是看起来sb的dp复杂度又不对的就是斜率优化。。当然一般是区间这样的问题?

\(dp[i]\)表示\([1,i]\)的最小费用,那么

$$\begin{align}dp[i]&=c[i]+min(dp[j]+\sum_{k\in[j+1,i]}{dis(k,i)\times p[k]})\\
&=c[i]+min(dp[j]+\sum_{k\in [j+1,i]}(dis(1,i)\times p[k]-dis(1,k)\times p[k]))\\
\end{align}$$

记一个\(p[k]\)的前缀和\(s1[k]\),\(dis[1,k]\times p[k]\)的前缀和\(s2[k]\)

$$\begin{align}dp[i]&=c[i]+min(dp[j]+dis(1,i)\times(s1[i]-s1[j])-(s2[i]-s2[j]))\\
&=c[i]+dis(1,i)\times s1[i]-s2[i]+min(dp[j]-dis(1,i)\times s1[j]+s2[j])\\
\end{align}$$

那么若\(l< r\)且\(l\)劣于\(r\),那么随着i增大也就是两个分别多减去几个\(s1\),且\(l\)减的少一些。那么\(l\)始终劣于\(r\)。决策单调性得证。

那么推一下斜率优化方程

$$dp[l]−dis(1,i)\times s1[l]+s2[l]>dp[r]-dis(1,i)\times s1[r]+s2[r]$$

$$dis(1,i)>\frac{(dp[r]+s2[r])-(dp[l]+s2[l])}{s1[r]-s1[l]}$$

就好办了

另外还有一点就是:所有斜率优化题不开ll就是作死【

1从下往上:没开ll,有一些地方没开ll,全开ll

当然实际上不用全开。。乘的时候注意不要让两个int相乘就可以了。

说点什么

您将是第一位评论人!

提醒
wpDiscuz