题解 | #[SDOI2012]任务安排#

和P3628 [APIO2010]特别行动队 差不多，都是序列拆成几个连续子段，每段都有一个权值，求权值最大/最小。

于是如法炮制。

$dp[i]:dp[i]:$前$ii$个的总代价最小值。

众所周知，后面的权值会被前面的决策影响。

所以每次更新的时候加上如果这样决策后面的数增加的权值。

于是枚举上一个断点。

设$t[i]t[i]$前缀和为$a[i]a[i]$，$c[i]c[i]$后缀和为$b[i]b[i]$。

$dp[i]={}_{j=0}^{i-1}dp[j]+b[j+1]\ast (s+a[i]-a[j])dp[i]=\backslash min\_\{j=0\}^\{i-1\}\; dp[j]+b[j+1]*(s+a[i]-a[j])$

于是20pts。

又众所周知，我是因为看到斜率优化才来做的。

所以考虑斜率优化。

$dp[i]=dp[j]+b[j+1]\ast s+b[j+1]\ast a[i]-b[j+1]\ast a[j]dp[i]=dp[j]+b[j+1]*s+b[j+1]*a[i]-b[j+1]*a[j]$

$-b[j+1]\ast a[i]+dp[i]=dp[j]+b[j+1]\ast s-b[j+1]\ast a[j]-b[j+1]*a[i]+dp[i]=dp[j]+b[j+1]*s-b[j+1]*a[j]$

设$x=-b[j+1],y=dp[j]+b[j+1]\ast s-b[j+1]\ast a[j]x=-b[j+1],y=dp[j]+b[j+1]*s-b[j+1]*a[j]$

于是就是一条斜率为$a[i]a[i]$的直线。

但是$a[i]a[i]$有可能不单调递增。

所以要维护整个下凸壳！

还要二分！！！

还卡精度！！！！

于是95pts了。

然后卡了114514年的精度后，过了。

这件事告诉我们：

判断斜率时用乘法是好习惯

顺便把弱化版水掉了。