CF311B题解

· · 题解

题解思路：

转化题意：

我们先求一下从第一座山到以后的每一座山的距离先求出来，也就是对 d_i 求一个前缀和。

那么现在的 d_i 就表示 1~i 的距离。

一个饲养员走到一个猫的山开始的时间为 s_i。

那么若 s_i + d_i \ge ti 那么饲养员才能把第 i 只小猫接上。

那么这只小猫的等待时间为：

s_i+\Delta t - (t_i-d_i)

那么我们用 a_i 来表示 t_i-a_i。

那么 a_i 就是要接走这只猫的最早出发时间。

那么我们把小猫的 a_i 从小到大排序。

那么饲养员出发的时候，每一次饲养员每次都要接走一批的小猫。

若一个饲养员要接走前 i 只小猫，那么就要在 a_i 时刻出发，当然这里的 a_i 是排序后的值。

那么前 i 等待的时间之和就是：

a_i-a_i+a_i-a_{i-1}+...+a_i-a_l =a_i*(i-l+1)-(Sum_i-Sum_{l-1})

其中 l 表示这段区间的左端点，i 就是右端点，Sum 就是 a_i 的前缀和。

那么就相当于有 m 个数，然后我们给他分成 p 组，然后每组的最后一个减去其他的差的和的最小值。

这样的话就转化成了和这道题类似了。

然后我们用斜率优化DP来做就可以了。

解法：

那么我们设 f_{j,i} 表示：前 i 只小猫分成 j 组的最小等待时间也就是用 j 个饲养员。

状态转移方程：

f_{j,i} = \max\{f_{j-1,k} + a_i \times (i-k) - (Sum_i-Sum_k)\}

我们把 i 和 j 看作常量，那么变形：

f_{j,i} = f_{j - 1 , k} - a_i \times k + Sum_k + a_i \times - Sum_i

那么和 k 有关的变量有：

f_{j-1,k},k,Sum_k

整理一下：

f_{j-1,k} + Sum_k = a_i \times k + f_{j,i} - a_i\times i + Sum_i

因为我们对 a_i 排序了，所以 a_i 是单调递增的。

那么 f_{j,i} - a_i \times i + Sum_i 就是截距。

那么 k 就是 x，f_{j-1,k} + Sum_k 是 y。

时间复杂度为 \mathcal{O}(pm)。

十年OI一场空，不开long long见祖宗！

AC CODE

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 100010 , M = 100010 , P = 110;
int n , m , p;
ll d[N] , t[N] , a[N] , s[N];
ll f[P][M];
int q[M];
ll get_y(int k , int j) {
    return f[j - 1][k] + s[k];
}
int main(){
    scanf ("%d%d%d" , &n , &m , &p);
    for (int i = 2; i <= n; ++ i){
        scanf ("%lld" , &d[i]);
        d[i] += d[i - 1];//预处理前缀和。
    }
    for (int i = 1; i <= m; ++ i){
        int h;
        scanf ("%d%lld" , &h , &t[i]);
        a[i] = t[i] - d[h];//a数组
    }
    sort (a + 1 , a + 1 + m);//排序
    for (int i = 1; i <= m; ++ i) s[i] += s[i - 1] + a[i];//a的前缀和
    memset (f , 0x3f , sizeof (f));
    for (int i = 0; i <= p; ++ i) f[i][0] = 0;
    for (int j = 1; j <= p; ++ j) {//DP
        int hh = 0 , tt = 0;
        q[0] = 0;
        for (int i = 1; i <= m; ++ i) {
            while (hh < tt && (get_y(q[hh + 1] , j) - get_y(q[hh] , j)) <= a[i] * (q[hh + 1] - q[hh])) ++ hh;
            int k = q[hh];
            f[j][i] = f[j - 1][k] - a[i] * k + s[k] + a[i] * i - s[i];
            while (hh < tt && (get_y(q[tt] , j) - get_y(q[tt - 1] , j)) * (i - q[tt]) >= (get_y(i , j) - get_y(q[tt] , j)) * (q[tt] - q[tt - 1])) -- tt;
            q[++ tt] = i;
        }
    }
    printf ("%lld\n" , f[p][m]);
    return 0;
}