题解 CF311B 【Cats Transport】

ww3113306 · 2018-11-09 17:03:03 · 题解

　　然后我们对t数组排个序，于是题意转化为了有m只猫，每只猫有一个权值t_{i},如果出发时间大于等于t_{i},则可以接到第i只猫。设出发时间为x，则接到第i只猫时，这只猫会等待x - t_{i}的时间。现在有p个人，要求为每个人指定一个时间使得所有猫的等待时间之和最小。

　　然后我们继续转化题意。

　　观察到每个人相当于会选择一只猫i，然后选择在t_{i}时刻出发，恰好接走这只猫，顺便可以接走其他可以被接走的猫。

　　为什么是每个人都必须选一只猫呢？

　　观察到如果一个人出发，没有任何一只猫是恰好被接到的，所有猫都是等了一会再被接走的，那么这个人为什么不早出发一点，恰好接走一些猫呢？这样不仅可以接走和上一种方案相同的猫，还可以减小等待时间。

　　于是现在题意转化为了有m只猫，每只猫有一个权值t_{i}。如果第x个人选择了第i只猫，上一个出发的人选了第j只猫，则这个人可以接走[j + 1, i]中的所有猫，并且代价为\sum_{k = j + 1}^{i}{t_{i} - t_{k}}。现在有p个人，要求为每个人指定一只猫使得所有猫的等待时间之和最小。

　　先化一下式子：(其中s[i]表示\sum_{k = 1}^{i}{t[k]})

　　\sum_{k = j + 1}^{i}{t_{i} - t_{k}} 　　= \sum_{k = j + 1}^{i}{t_{i}} - \sum_{k = j + 1}^{i}{t_{k}} 　　= (i - j) t_{i} - (s[i] - s[j])

　　于是我们设f[i][j]表示DP到第i个人，这个人选择了第j只猫的最小代价。

　　然后暴力枚举i，j，转移的时候再暴力枚举前一个人选了哪只猫即可。

　　但是这样的复杂度是pm^2的，观察到我们优化到pm就可以过了，又注意到式子中有一个跟i相关的量和一个跟j相关的量的乘积，我们考虑一下斜率优化。

　　我们先化一波式子。

f[i][j] = f[i - 1][k] + (j - k) t_{j} - (s[j] - s[k])

\Rightarrow f[i][j] = f[i - 1][k] + jt_{j} - kt_{j} - s[j] + s[k]

\Rightarrow -s[k] - f[i - 1][k] = -kt_{j} + jt_{j} - s[j] - f[i][j]

\Rightarrow s[k] + f[i - 1][k] = t_{j}k - jt_{j} + s[j] + f[i][j]

　　代入y = kx + b可以得到y = s[k] + f[i - 1][k], x = k, K = t_{j}, b = -jt_{j} + s[j] + f[i][j]。

　　斜优式子已经出来了，现在就是要证明单调性了。

　　首先K = t_{j}本来就是排好序的，所以从小到大枚举j，所以每次加入的决策点(x, y)中的x = j肯定是递增的，t_{j}肯定也是递增的。

　　所以就可以直接上斜优了。　　

　　然而写的时候发现我对计算几何一无所知，，，凸包维护错了调了好久QAQ

　　~~发现第一次写的时候证的单调性不是斜优需要的那个单调性。。。。。更新一下，现在证的应该是斜优需要的那个了~~

#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 110
#define ac 120000
#define LL long long

int n, m, p, Head, tail, now;
LL ans;
LL f[AC][ac], d[ac], t[ac], sum[ac], s[ac];

inline int read()
{
    int x = 0;char c = getchar();
    while(c > '9' || c < '0') c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x;
}

inline void pre()
{
    n = read(), m = read(), p = read();
    for(R i = 2; i <= n; i ++) d[i] = read() + d[i - 1];//顺便统计一下前缀和
    for(R i = 1; i <= m; i ++)
    {
        LL tmp = read();
        t[i] = read() - d[tmp]; 
    }
    sort(t + 1, t + m + 1);
    for(R i = 1; i <= m; i ++) sum[i] = sum[i - 1] + t[i];//这个要放在排好序之后
}

inline void upmin(LL &a, LL b){
    if(b < a) a = b;
}

inline LL Y(int k){
    return sum[k] + f[now][k];
}

inline LL cross(int a, int b, int c){//算叉积
    LL x1 = a - b, x2 = b - c, y1 = Y(a) - Y(b), y2 = Y(b) - Y(c);
    return x1 * y2 - x2 * y1;
}

inline LL cal(int x, int k){//算出y - kx,表示b的大小
    return Y(x) - t[k] * x;
}

inline void work()
{
    for(R i = 1; i <= m; i ++) 
        f[1][i] = i * t[i] - sum[i];//先算出第一个人的
    ans = f[1][m];
    for(R i = 2; i <= p; i ++)//枚举人
    {
        Head = 1, tail = 0, now = i - 1;
        s[++tail] = 0;//0也是一个决策点
        for(R j = 1; j <= m; j ++)//枚举当前选择的猫
        {
            while(Head < tail && cal(s[Head + 1], j) < cal(s[Head], j)) ++ Head;
            int x = s[Head];
            f[i][j] = f[i - 1][x] + (j - x) * t[j] - sum[j] + sum[x];
            while(Head < tail && cross(j, s[tail], s[tail - 1]) > 0) -- tail;
            s[++ tail] = j;
        }
        upmin(ans, f[i][m]);
    }
    printf("%lld\n", ans);
} 

int main()
{
    freopen("in.in", "r", stdin);
    pre();
    work();
    fclose(stdin);
    return 0;
}

题解 CF311B 【Cats Transport】

广告