动态规划——斜率优化DP

状态表示f[i]:
集合：完成前i个任务且第i个任务为最后一个批次最后一个任务的方案。
属性：min
状态计算：
f [ i ] = m i n { f [ j ] + s u m t [ i ] × ∑ j + 1 i w [ u ] + s × ∑ j + 1 n w [ i ] } f[i]=min\{f[j]+sumt[i] ×\sum_{j+1}^{i}w[u]+s×\sum_{j+1}^{n}w[i]\} f[i]=min{f[j]+sumt[i]×∑j+1i​w[u]+s×∑j+1n​w[i]}$(0\le j<i)$
f [ i ] = m i n { f [ j ] + s u m t [ i ] × ( s u m c [ i ] − s u m c [ j ] ) + s × ( s u m c [ n ] − s u m c [ j ] ) } f[i]=min\{f[j]+sumt[i] ×(sumc[i]-sumc[j])+s×(sumc[n]-sumc[j])\} f[i]=min{f[j]+sumt[i]×(sumc[i]−sumc[j])+s×(sumc[n]−sumc[j])}$(0\le j<i)$

时间复杂度为$O(n^2)$

#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010;
typedef long long ll;
ll f[N];
ll sumt[N], sumc[N];
int n, s;
int main()
{
    cin >> n >> s;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld%lld", &sumt[i], &sumc[i]);
        sumt[i] += sumt[i - 1];
        sumc[i] += sumc[i - 1];
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 0; j < i; j ++ )
        {
            f[i] = min(f[i], f[j] + sumt[i] * (sumc[i] - sumc[j]) + s * (sumc[n] - sumc[j]));
        }
    }
    cout << f[n];
    return 0;
}

我们对上一题得到的状态转移方程 f [ i ] = m i n { f [ j ] + s u m t [ i ] × ( s u m c [ i ] − s u m c [ j ] ) + s × ( s u m c [ n ] − s u m c [ j ] ) } f[i]=min\{f[j]+sumt[i] ×(sumc[i]-sumc[j])+s×(sumc[n]-sumc[j])\} f[i]=min{f[j]+sumt[i]×(sumc[i]−sumc[j])+s×(sumc[n]−sumc[j])}$(0\le j<i)$进行编变形。

$f[i]=f[j]+sumt[i]\times sumc[i]-sumt[i]\times sumc[j]+s\times sumc[n]-s\times sumc[j]$
$f[i]=f[j]-sumt[i]\times sumc[j]-s\times sumc[j]+sumt[i]\times sumc[i]+s\times sumc[n]$
$f[i]=f[j]-(sumt[i]+s)\times sumc[j]+sumt[i]\times sumc[i]+s\times sumc[n]$
移项得到
$f[j]=(sumt[i]+s)\times sumc[j]-sumt[i]\times sumc[i]-s\times sumc[n]+f[i]$
上式是$y=kx+b$的形式，$y$是$f[j]$,$k$是$(sumt[i]+s)$,$x$是$sumc[j]$,$b$是$f[i]-sumt[i]\times sumc[i]-s\times sumc[n]$。

我们的目标是求$f[i]$的最小值，因为$b$中除了$f[i]$以外的部分是常量，也正因此等价于去想办法让截距最小。因为$k$也是一个常量， 所以本问题又可以转化为给定一条斜率固定的直线去找过一个$(x,y)$点对,使得$b$最小。$(x,y)$点对有$(sumc[0],f[0])$，$(sumc[1],f[1])$,…,$(sumc[i-1],f[i-1])$。

给出结论，无论斜率如何变化，最小值一定是取到凸包下边界的一个点。
具体来说，最小值一定是第一个大于直线斜率的线段头部$k_i$的点。

分析题目：
1.,$k$是$(sumt[i]+s)$,单调递增。
2.新加入点的横坐标也是单调递增。
由于斜率$k$是单调递增的，也就是说，如果当前的斜率$k$大于队头两个点的斜率时，那么一开始的点就可以彻底删除，在以后也不会用到，所以凸包中的点可以用单调队列来维护。

维护一个凸包的做法：
1.查询的时候，把队头小于当前斜率k的点删掉。
$\frac{f[q[hh+1]-f[q[hh]}{sumc[q[hh+1]]-sumc[q[hh]}\le sumt[i]+s$
2.插入的时候，把不在凸包上的点删掉。
$\frac{f[q[tt]-f[q[tt-1]}{sumc[q[hh]]-sumc[q[hh-1]}\ge \frac{f[i]-f[q[tt]]}{sumc[i]-sumc[q[hh]]}$

时间复杂度为$O(n)$

#include <iostream>
using namespace std;
typedef long long ll;
const int N = 300010;
int q[N];
ll t[N], c[N];
ll f[N];
int n, s;
int main()
{
    cin >> n >> s;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld%lld", &t[i], &c[i]);
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        while (hh < tt && f[q[hh + 1]] - f[q[hh]] <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]])) hh ++ ;
        int j = q[hh];
        f[i] = f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]);
        while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]])) tt -- ;
        q[++ tt] = i;
    }
    cout << f[n];
    return 0;
}

和上一题不同的是， 本题中机器的工作时间可以为负数，也正因此斜率$k$并不是随着$i$单调递增的了，上一题中，对于凸包的头部和尾部均使用单调队列来处理，本题则需要使用二分去找到合适的点对，对尾部的处理同样使用单调队列。

#include <iostream>
using namespace std;
const int N = 300010;
typedef long long ll;
ll t[N], c[N];
ll f[N];
int q[N];
int n, s;
int main()
{
    cin >> n >> s;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld%lld", &t[i], &c[i]);
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }
    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int l = hh, r = tt;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (f[q[mid + 1]] - f[q[mid]] > (double)(t[i] + s) * (c[q[mid + 1]] - c[q[mid]])) r = mid;
            else l = mid + 1;
        }
        int j = q[l];
        f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
        while (hh < tt && (double)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (double)(f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]])) tt -- ;
        q[++ tt] = i;
    }
    cout << f[n];
    return 0;
}

每一只小猫都会对应一个最早出发时间$a[i]=t[i]-d[h[i]]$，也就是结束玩耍的时间减去到1号山的距离。当我们处理完$a$数组后，对数组$a$进行一个从小打到的排序。这样一来，相邻一段猫肯定是要由一个饲养员接走的，饲养员的出发时间就是这一段最后一只猫对应的数组$a$的值。
状态表示f[i][j]:
集合：对于前$i$只猫，安排$j$个饲养员去接猫的所有方案。
属性：min
状态计算：
f [ i ] [ j ] = m i n { f [ k ] [ j − 1 ] + ∑ k + 1 i ( a i − a u ) } f[i][j]=min\{f[k][j-1]+\sum_{k+1}^{i}(a_i-a_u)\} f[i][j]=min{f[k][j−1]+∑k+1i​(ai​−au​)}$(0\le k<i)$
f [ i ] [ j ] = m i n { f [ k ] [ j − 1 ] + ∑ k + 1 i a i − ∑ k + 1 i a u } f[i][j]=min\{f[k][j-1]+\sum_{k+1}^{i}a_i-\sum_{k+1}^{i}a_u\} f[i][j]=min{f[k][j−1]+∑k+1i​ai​−∑k+1i​au​}$(0\le k<i)$
f [ i ] [ j ] = m i n { f [ k ] [ j − 1 ] + ( i − k ) a i − ( s [ i ] − s [ k ] ) } f[i][j]=min\{f[k][j-1]+(i-k)a_i-(s[i]-s[k])\} f[i][j]=min{f[k][j−1]+(i−k)ai​−(s[i]−s[k])}$(0\le k<i)$
移项得:
$f[k][j-1]+s[k]=a[i]\times k+f[i][j]+s[i]-ia[i]$
至此，本题就转换为了任务安排2。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 100010;
const int P = 110;
ll f[P][N];
ll a[N];
ll s[N];
int d[N];
int q[N];
int n, m, p;
ll get_y(int j, int k)
{
    return f[j - 1][k] + s[k];
}
int main()
{
    cin >> n >> m >> p;
    for (int i = 2; i <= n; i ++ )
    {
        scanf("%d", &d[i]);
        d[i] += d[i - 1];
    }
    for (int i = 1; i <= m; i ++ )
    {
        ll h, t;
        scanf("%lld%lld", &h, &t);
        a[i] = t - d[h];
    }
    sort(a + 1, a + m + 1);
    for (int i = 1; i <= m; i ++ )
    {
        s[i] = a[i];
        s[i] += s[i - 1];
    }
    memset(f,0x3f,sizeof f);
    for(int i = 0;i <= p;i ++)
        f[i][0] = 0;

    for (int i = 1; i <= p; i ++ )
    {
        int hh = 0, tt = 0;
        for (int j = 1; j <= m; j ++ )
        {
            while (hh < tt && get_y(i, q[hh + 1]) - get_y(i, q[hh]) <= (q[hh + 1] - q[hh]) * a[j]) hh ++;
            int k = q[hh];
            f[i][j] = f[i - 1][k] + (j - k) * a[j] - (s[j] - s[k]);
            while (hh < tt && (get_y(i, q[tt]) - get_y(i, q[tt - 1])) * (j - q[tt]) >= (get_y(i, j) - get_y(i, q[tt])) * (q[tt] - q[tt - 1])) tt --;
            q[++ tt] = j;
            
        }
    }
    cout << f[p][m];
    return 0;
}