首先山脚的那个一定得建。

因为只能往山脚运，所以考虑从后往前dp

dp[i]dp[i]：在ii建一个仓库，后缀最小的值。

所以

dp[i]=c[i]+j=i+1n(dp[j]+∑k=i+1j−1p[k]×(x[j]−x[k]) )dp[i]=c[i]+\min_{j=i+1}^{n}(dp[j]+\sum_{k=i+1}^{j-1}p[k] \times (x[j]-x[k])\ )

于是30pts。

观察这个式子，

dp[i]=c[i]+j=i+1n(dp[j]+∑k=i+1j−1p[k]×(x[j]−x[k]) )dp[i]=c[i]+\min_{j=i+1}^{n}(dp[j]+\sum_{k=i+1}^{j-1}p[k] \times (x[j]-x[k])\ )

=c[i]+j=i+1n(dp[j]+∑k=i+1j−1p[k]×x[j]−p[k]∗x[k] )=c[i]+\min_{j=i+1}^{n}(dp[j]+\sum_{k=i+1}^{j-1}p[k] \times x[j] - p[k]*x[k]\ )

而p[k]∗x[k]p[k]*x[k]可以预处理。

设a[i]=p[i]∗x[i]a[i]=p[i]*x[i]的前缀和,b[i]b[i]是pp的前缀和。

所以 dp[i]=c[i]+j=i+1n(dp[j]+(b[j−1]−b[i])×x[j]−a[j−1]+a[i])dp[i]=c[i]+\min_{j=i+1}^{n}(dp[j]+(b[j-1]-b[i]) \times x[j]-a[j-1]+a[i] )

于是50pts。

dp[i]=(dp[j]+(b[j−1]−b[i])×x[j]−a[j−1]+a[i])+c[i]dp[i]=(dp[j]+(b[j-1]-b[i]) \times x[j]-a[j-1]+a[i] )+c[i]

=dp[j]+b[j−1]∗x[j]−b[i]∗x[j]−a[j−1]+a[i]+c[i]=dp[j]+b[j-1]*x[j]-b[i]*x[j]-a[j-1]+a[i]+c[i]

用另一种阳间一点的方法分析吧。

若j的决策优于k

那么

dp[j]+b[j−1]∗x[j]−b[i]∗x[j]−a[j−1]+a[i]+c[i]<dp[k]+b[k−1]∗x[j]−b[i]∗x[k]−a[k−1]+a[i]+c[i]dp[j]+b[j-1]*x[j]-b[i]*x[j]-a[j-1]+a[i]+c[i]<dp[k]+b[k-1]*x[j]-b[i]*x[k]-a[k-1]+a[i]+c[i]

dp[j]+b[j−1]∗x[j]−b[i]∗x[j]−a[j−1]<dp[k]+b[k−1]∗x[j]−b[i]∗x[k]−a[k−1]dp[j]+b[j-1]*x[j]-b[i]*x[j]-a[j-1]<dp[k]+b[k-1]*x[j]-b[i]*x[k]-a[k-1]

(dp[j]−a[j−1])−(dp[k]−a[k−1])+b[j−1]∗x[j]−b[i]∗x[j]<b[k−1]∗x[k]−b[i]∗x[k](dp[j]-a[j-1])-(dp[k]-a[k-1])+b[j-1]*x[j]-b[i]*x[j]<b[k-1]*x[k]-b[i]*x[k]

(dp[j]−a[j−1])−(dp[k]−a[k−1])+b[j−1]∗x[j]−b[k−1]∗x[k]<b[i]∗x[j]−b[i]∗x[k](dp[j]-a[j-1])-(dp[k]-a[k-1])+b[j-1]*x[j]-b[k-1]*x[k]<b[i]*x[j]-b[i]*x[k]

(dp[j]−a[j−1])−(dp[k]−a[k−1])+b[j−1]∗x[j]−b[k−1]∗x[k]<b[i]∗(x[j]−x[k])(dp[j]-a[j-1])-(dp[k]-a[k-1])+b[j-1]*x[j]-b[k-1]*x[k]<b[i]*(x[j]-x[k]) (dp[j]−a[j−1]+b[j−1]∗x[j])−(dp[k]−a[k−1]+b[k−1]∗x[k])x[j]−x[k]<b[i]\dfrac{(dp[j]-a[j-1]+b[j-1]*x[j])-(dp[k]-a[k-1]+b[k-1]*x[k])}{x[j]-x[k]}<b[i]

设X(i)=x[i],Y(i)=dp[i]−a[i−1]+b[i−1]∗x[i]X(i)=x[i],Y(i)=dp[i]-a[i-1]+b[i-1]*x[i]

于是 Y(j)−Y(k)X(j)−X(k)<b[i]\dfrac{Y(j)-Y(k)}{X(j)-X(k)}<b[i]

斜率优化。