题解 CF311B Cats Transport

前置芝士：斜率优化
剥下这道题的外壳，让它变为一道裸的斜率优化。
很容易想到状态，但复杂度显然过不去，也没有单调性，只能自己创造。
令
$$c[i] = t - sum[i],sum[i] = \sum_{j = 1} ^{i} d[j]$$
如果出发时间为t,那么 t - c[i] 即是等待时间
将 c 数组排序后，带走其中一个即可以带走旁边几个，那就是变成了连续选择，c排序后有了单调性，那么转移式就成了
dp[k][i]表示第 k 个饲养员，到 i 这个地方取猫的最小代价
$$dp[k][i] = min(dp[k - 1][j] + \sum_{t = j + 1}^ic[i] - c[t])(j \le i )$$
发现之中有前缀和
令
$$S_i = \sum_{t = 1}^ic[t]$$
那么化简式子后就成了一个标准的斜率优化
$$dp[k - 1][j] + S_j = c[i] * j + dp[k][i] - c[i] * i$$

具体实现不懂的

#include<bits/stdc++.h>

using namespace std;

#define N 100001

long long f[101][N];

struct node {

    int k,las;

}p[N * 101];

int l = 1,r = 0;

int n,m,q;

long long sumd[N];

struct cats {

    long long a,sum;

}c[N];

bool cmp(cats x,cats y) {

    return x.a < y.a;

}

inline bool checkhead(int x1,int x2,int pos,int peo) {

    if(l + 1 > r) return false;

    peo--;

    if(f[peo][x2] - f[peo][x1] + c[x2].sum - c[x1].sum <= (x2 - x1) * c[pos].a) return true;

    return false;

}

inline bool check(int x1,int x2,int pos,int peo) {

    if(r - 1 < l) return false;

    peo--;

    if((f[peo][x2] - f[peo][x1] + c[x2].sum - c[x1].sum) * (pos - x2) <= (f[peo][pos] - f[peo][x2] + c[pos].sum - c[x2].sum) * (x2 - x1)) {

        return true;

    }

    return false;

}

int main() {

    scanf("%d %d %d", &n, &m, &q);

    for(int i = 2;i <= n;i++) {

        scanf("%d", &sumd[i]);

        sumd[i] += sumd[i - 1];

    }

    for(int i = 1;i <= m;i++) {

        int pos,t;

        scanf("%d %d", &pos, &t);

        c[i].a = t - sumd[pos];

    }

    int cnt = 0;

    sort(c + 1,c + m + 1,cmp);

    for(int i = 1;i <= m;i++)  {

        c[i].sum = c[i - 1].sum + c[i].a;

    }

    for(int i = 1;i <= m;i++) {

        f[1][i] = i * c[i].a - c[i].sum;

    }

    f[0][0] = 0;

    for(int i = 2;i <= q;i++) {

        l = 1,r = 0;

        p[++r].k = 0;

        c[0].a = 0,c[0].sum = 0;

        for(int j = 1;j <= m;j++) {

            while(l <= r && checkhead(p[l].k,p[l + 1].k,j,i)) {

                l++;

            }

            int k = p[l].k;

            f[i][j] = f[i - 1][k] + c[k].sum + c[j].a * j - c[j].a * k - c[j].sum;

            while(l <= r && check(p[r].k,p[r - 1].k,j,i)) {

                r--;

            }

            p[++r].k = j;

        }

    }

    cout<<f[q][m];

    return 0;

}

巴特西

题解 CF311B Cats Transport

最新文章

热门文章