【poj1180】Batch Scheduling

题意：

给定$n$n个（≤10000）需依次完成的任务，你可以将它们分成若干段处理。每处理一个段，首先需要有$s$s的准备时间。处理一个段的费用为已花费的时间（从第一段任务的准备阶段开始计时）乘以段中每一个任务的权值$f_i$fi​（题解中记作$v[i]$v[i]）之和。求完成这些任务的最小费用。

题解

刚开始，很容易想到正着做。然而，尝试了一通，发现难度直线上升。于是，我们可以倒着看。
设$f[i]$f[i]为完成$[i,n]$[i,n]的任务所需的最小费用，$s1[i]$s1[i]为任务用时$t[i]$t[i]的后缀和, $s2[i]$s2[i]为任务用时$v[i]$v[i]的后缀和。
则有：
$f[i]=min\{f[j]+(s+s1[i]-s1[j])*s2[i]|i&lt;j&lt;=n+1\},f[n+1]=s1[n+1]=s2[n+1]=0$f[i]=min{f[j]+(s+s1[i]−s1[j])∗s2[i]∣i<j<=n+1},f[n+1]=s1[n+1]=s2[n+1]=0
如何理解这个方程呢？我们画画图看一下(鼠标写字真心累)：

$f[j]$f[j]已将$j$j段的时间和算了进来：

观察dp式：
$f[i]=min(f[j]+(s+s1[i]-s1[j])*s2[i])$f[i]=min(f[j]+(s+s1[i]−s1[j])∗s2[i])
若将$f[j]$f[j]拆开，然后运用乘法分配律：
$f[i]=min\{S[i]s2[j]+(s2[i]-s2[j])(s+s1[i]-s1[j])\}，S[i]表示完成i以后的任务的总时间$f[i]=min{S[i]s2[j]+(s2[i]−s2[j])(s+s1[i]−s1[j])}，S[i]表示完成i以后的任务的总时间
正好是f[i]的值。换句话说，我们可以将黑线段的时间和与蓝线段合并：

就得到了该段的总时间。
开始优化：
假设$j&#x27;&gt;j$j′>j且$p(j&#x27;)&gt;p(j)$p(j′)>p(j)（表示该决策点的优劣度，越大越优），则有：
$f[j]+(s+s1[i]-s1[j])*s2[i]&gt;f[j&#x27;]+(s+s1[i]-s1[j&#x27;])*s2[i]$f[j]+(s+s1[i]−s1[j])∗s2[i]>f[j′]+(s+s1[i]−s1[j′])∗s2[i]
整理得:
$s2[i](s1[j&#x27;]-s1[j])&gt;f[j&#x27;]-f[j]$s2[i](s1[j′]−s1[j])>f[j′]−f[j]
令$\Delta x=s1[j&#x27;]-s1[j], \Delta y=f[j&#x27;]-f[j]$Δx=s1[j′]−s1[j],Δy=f[j′]−f[j],则$s2[i]\Delta x&gt;\Delta y$s2[i]Δx>Δy
由于在dp过程中，$s2[i]$s2[i]依旧单增，所以我们需要维护一个下凸包。这快把我给坑死了

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int mn = 10005;
ll f[mn], s1[mn], s2[mn];
int q[mn], h, t;
inline ll dx(int i, int j)
{
    return s1[i] - s1[j];
}
inline ll dy(int i, int j)
{
    return f[i] - f[j];
}
int main()
{
    int n, m, i;
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        scanf("%lld%lld", &s1[i], &s2[i]);
    for(i = n - 1; i; i--)
        s1[i] += s1[i + 1], s2[i] += s2[i + 1];
    q[1] = n + 1, h = t = 1;
    for(i = n; i; i--)
    {
        while(h < t && s2[i] * dx(q[h], q[h + 1]) < dy(q[h], q[h + 1]))
            h++;
        f[i] = f[q[h]] + (s1[i] - s1[q[h]] + m) * s2[i];
        while(h < t && dx(q[t], i) * dy(q[t - 1], q[t]) > dx(q[t - 1], q[t]) * dy(q[t], i))
            t--;
        q[++t] = i;
    }
    printf("%lld\n", f[1]);
}