运输小猫

原题链接

题目描述

小 \(S\) 是农场主，他养了 \(M\) 只猫，雇了 \(P\) 位饲养员。

农场中有一条笔直的路，路边有 \(N\) 座山，从 \(1\) 到 \(N\) 编号。

第 \(i\) 座山与第 \(i−1\) 座山之间的距离为 \(D_i\)。

饲养员都住在 \(1\) 号山。

有一天，猫出去玩。

第 \(i\) 只猫去 \(H_i\) 号山玩，玩到时刻 \(T_i\) 停止，然后在原地等饲养员来接。

饲养员们必须回收所有的猫。

每个饲养员沿着路从 \(1\) 号山走到 \(N\) 号山，把各座山上已经在等待的猫全部接走。

饲养员在路上行走需要时间，速度为 \(1\) 米/单位时间。

饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。

例如有两座相距为 \(1\) 的山，一只猫在 \(2\) 号山玩，玩到时刻 \(3\) 开始等待。

如果饲养员从 \(1\) 号山在时刻 \(2\) 或 \(3\) 出发，那么他可以接到猫，猫的等待时间为 \(0\) 或 \(1\)。

而如果他于时刻 \(1\) 出发，那么他将于时刻 \(2\) 经过 \(2\) 号山，不能接到当时仍在玩的猫。

你的任务是规划每个饲养员从 \(1\) 号山出发的时间，使得所有猫等待时间的总和尽量小。

饲养员出发的时间可以为负。

思路斜率优化DP+排序

前置知识：任务安排 2

首先用前缀和 \(d_i\) 表示第 \(1\) 座山到第 \(i\) 座山的距离。

那么每只猫恰好完好就被接走的饲养员出发时间即为：\(t_i-d_{h_i}\)。

令 \(a_i=t_i-d_{h_i}\)，表示第 \(i\) 只猫被接走的最早时间。

那么对于第 \(T\) 时刻出发的饲养员，他可以接走的猫满足：\(a_i\le T\)。

动态规划

\(dp[i][j]\) 状态分析

集合： 第 \(i\) 个饲养员接回 \(j\) 只猫等待时间的所有方案；
属性： 所有猫等待时间总和的最小值；

状态计算： 考虑前 \(i-1\) 个接走了 \(k\) 只猫，那么第 \(i\) 个饲养员接走 \(j\) 只猫的等待时间总和 \(cost=\sum_{u=k+1}^{j}(T-a_u)\)。

要是 \(cost\) 尽可能的小，贪心的想，\(T\) 的值取 \(a_j\)即可。

那么可以推出状态转移的表达式，即为

\[dp[i][j]=dp[i-1][k]+\sum_{u=k+1}^{j}(a_j-a_u)\]

令 \(s_i = \sum_{j=1}^i a_i\)，展开表达式，可得

\[dp[i][j]=dp[i-1][k]+(j-k)\times a_j-s_j+s_k\]

取出表达式中关于 \(k\) 的多项式，得

\[dp[i][j]=dp[i-1][k]+s_k-a_j\times k-s_j+j\times a_j\]

令 \(\begin{cases} y(k)=dp[i-1][k]+s_k \\ x(k)=k \\ K=a_j \\ b=dp[i][j]+s_j-j\times a_j \end{cases}\) ，那么上述多项式可以利用斜率优化DP来求解。

查询时，队头小于当前斜率上的点全删。即 \(\dfrac{y_{q[hh+1]}-y_{q[hh]}}{x_{q[hh+1]}-x_{q[hh]}}\le a_j\)
插入时，队尾不在凸包上的点全删。即 \(\dfrac{y_{q[tt]}-y_{q[tt-1]}}{x_{q[tt]}-x_{q[tt-1]}}\ge\dfrac{y_{j}-y_{q[tt-1]}}{x_{j}-x_{q[tt-1]}}\)

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 100010, P = 110;

int n, m, p;
LL d[N], a[N], dp[P][N], s[N];
int q[N];

// dp[i][j]: 第i个饲养员接回j只猫等待时间的最小值

LL y(int k, int i) {
    return dp[i - 1][k] + s[k];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> p;
    for (int i = 2; i <= n; i++) {
        cin >> d[i];
        d[i] += d[i - 1];
    }

    for (int i = 1; i <= m; i++) {
        int t, h;
        cin >> h >> t;
        a[i] = t - d[h];
    }

    sort(a + 1, a + 1 + m);

    for (int i = 1; i <= m; i++)
        s[i] = s[i - 1] + a[i];

    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i <= p; i++)
        dp[i][0] = 0;

    for (int i = 1; i <= p; i++) {
        int hh = 0, tt = 0;
        for (int j = 1; j <= m; j++) {
            // query
            while (hh < tt && y(q[hh + 1], i) - y(q[hh], i) <= a[j] * (q[hh + 1] - q[hh])) hh++;
            int k = q[hh];

            // get answer
            dp[i][j] = dp[i - 1][k] + s[k] - a[j] * k - s[j] + j * a[j];

            // insert
            while (hh < tt && (y(q[tt], i) - y(q[tt - 1], i)) * (j - q[tt]) >=
                    (y(j, i) - y(q[tt], i)) * (q[tt] - q[tt - 1])) tt--;
            q[++tt] = j;
        }
    }

    cout << dp[p][m] << endl;

    return 0;
}

运输小猫

题目描述

思路 斜率优化DP+排序

动态规划

代码

思路斜率优化DP+排序