P4360 [CEOI2004]锯木厂选址

P4360 [CEOI2004]锯木厂选址

有点不像 DP 题，但是确实需要斜率优化。

先对数据进行处理，用 $d$ 表示到最下面的锯木厂的距离，对 $w$ 做前缀和。
$$
d _ i = \sum _ {j = 1} ^ n d _ j
$$

$$
s _ i = \sum _ {i = 1} ^ i w _i
$$

由题意可以得到答案为
$$
\begin {aligned}
& \min _ {a < b} \{\sum _ {i = 1} ^ a w _ i(d _ i - d _ a) + \sum _ {i = a + 1} ^ b w _ i(d _ i - d _ b) + \sum _ {i = b +1} ^ n w _ id _ i \} \\
= & \sum _ {i = 1} ^ n w _ i * d _ i - \max _ {a < b} \{\sum _ {i = 1} ^ a w _ i d _ a + \sum _ {i = a + 1} ^ b w _ i d _ b \} \\
= & \sum _ {i = 1} ^ n w _ i * d _ i - \max _ {a < b} \{ s _ a d _ a + (s _ b - s _ i) d _ b \} \\
\end {aligned}
$$
如果现在确定了第二个锯木厂 $i$ ，则当前最小费用为 $\displaystyle \sum _ {i = 1} ^ n w _ i * d _ i -$
$$
f _ i = \max _ {j <i} \{ s _ j d _ j + (s _ i - s _ j) d _ i \}
$$
将其化为斜率优化的一般形式：
$$
f _ i - s _ i d _ i = \max _ {j <i} \{ s _ j d _ j - s _ j d _ i \}
$$
维护上凸包即可。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e4 + 10;
int hd = 1, tl, q[N];
int n;
LL w[N], s[N], d[N], f[N];
double slp(int a, int b)
{
    return (double)(d[a] * s[a] - d[b] * s[b]) / (s[a] - s[b]);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &w[i], &d[i]);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + w[i];
    for (int i = n - 1; i; i--)
        d[i] += d[i + 1];
    for (int i = 1; i <= n; i++)
    {
        while (hd < tl && slp(q[hd], q[hd + 1]) > d[i])
            hd++;
        f[i] = d[q[hd]] * s[q[hd]] + d[i] * (s[i] - s[q[hd]]);
        while (hd < tl && slp(q[tl - 1], q[tl]) < slp(q[tl], i))
            tl--;
        q[++tl] = i;
    }
    LL tot = 0, mx = 0;
    for (int i = 1; i <= n; i++)
        tot += d[i] * w[i];
    for (int i = 1; i <= n; i++)
        mx = max(mx, f[i]);
    printf("%lld", tot - mx);
    return 0;
}