LibreOJ 10192 「CEOI2004」锯木厂选址

首先写出朴素的式子：fi=min1≤j<i(cost−sumjdisj−(sumi−sumj)disi)。
其中 fi 表示第二个锯木厂建在 i 处的最小代价，sumi=i∑j=1wj,disi=n∑j=idj，cost 表示只有山脚的锯木厂的代价。
这貌似不是个 DP？不过也可以用斜率优化解决！

对于 1≤k<j<i，假设选 j 优于选 k，即 cost−sumjdisj−(sumi−sumj)disi≤cost−sumkdisk−(sumi−sumk)disisumjdisj+(sumi−sumj)disi≥sumkdisk+(sumi−sumk)disisumjdisj+sumidisi−sumjdisi≥sumkdisk+sumidisi−sumkdisisumjdisj−sumjdisi≥sumkdisk−sumkdisisumjdisj−sumkdisk≥(sumj−sumk)disisumjdisj−sumkdisksumj−sumk≥disi

按照套路，单调队列维护上凸包即可。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e4;
int n;
int q[N + 5],head,tail;
long long sum[N + 5],dis[N + 5],cost,f[N + 5],ans = 0x3f3f3f3f3f3f3f3f;
inline double slope(int x,int y)
{
    return (double)(sum[x] * dis[x] - sum[y] * dis[y]) / (sum[x] - sum[y]);
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%lld%lld",sum + i,dis + i),sum[i] += sum[i - 1];
    for(register int i = n;i;--i)
        dis[i] += dis[i + 1],cost += (sum[i] - sum[i - 1]) * dis[i];
    q[head = tail = 1] = 1;
    for(register int i = 2;i <= n;++i)
    {
        for(;head < tail && slope(q[head],q[head + 1]) >= dis[i];++head);
        ans = min(ans,f[i] = cost - sum[q[head]] * dis[q[head]] - (sum[i] - sum[q[head]]) * dis[i]);
        for(;head < tail && slope(q[tail - 1],q[tail]) <= slope(q[tail],i);--tail);
        q[++tail] = i;
    }
    printf("%lld\n",ans);
}