CodeForces 311 B Cats Transport 斜率优化DP

题目传送门

题意：现在有n座山峰，现在 i-1 与 i 座山峰有 di长的路，现在有m个宠物，分别在hi座山峰，第ti秒之后可以被带走，现在有p个人，每个人会从1号山峰走到n号山峰，速度1m/s。现在你可以安排好这p个人的出发时间，问所有宠物的等待时间是多少。

题解：

斜率优化DP

我们知道一个人出发之后，该宠物的等待时间就已经决定了。

所以我们可以把每个宠物的0等待时间算出来，即 A[i] = t[i] - d[h[i]]， d为1-h[i]的距离

然后把A[i]排序之后，就可以得到一个出发时间的递增序列。

dp[i] = dp[j]+ A[i]*(i-j) - (S[i] - S[j]);

dp[j] + S[j] = A[i] * j - A[I]*i + S[i]

我们就可以维护一个(j, dp[j]+S[j])的下凸壳。

然后对于这个题目来说， p个人，那么则需要dp p 次，每一次的答案都是通过上一层转移过来的，即 dp[k][i] = dp[k-1][j] + A[i]*(i-j) - (S[i] - S[j]);

然后对于这个过程我们可以用滚动数组去优化空间。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 2e5 + ;

LL A[N], S[N], f[N], ff[N];

int d[N], q[N];

int L, R;

int main(){

    int n, m, p;

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

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

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

        d[i] += d[i-];

    }

    int h, t;

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

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

        A[i] = t - d[h];

    }

    sort(A+, A++m);

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

        S[i] = S[i-] + A[i];

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

        f[i] = A[i]*i - S[i];

    L = R = ;

    q[] = ;

    for(int k = ; k <= p; ++k){

        L =  R = ;

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

            while(L < R && (f[q[R]]+ S[q[R]] - f[q[R-]]-S[q[R-]]) * (i - q[R]) >= (f[i]+ S[i] - f[q[R]]-S[q[R]]) * (q[R] - q[R-])) --R;

                    q[++R] = i;

            while(L < R && ((f[q[L+]]+ S[q[L+]] - f[q[L]]-S[q[L]]) <= A[i] * (q[L+]-q[L]))) ++L;

            ff[i] = f[q[L]] + A[i]*(i-q[L]) - (S[i] - S[q[L]]);

        }

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

            f[i] = ff[i];

    }

    cout << f[m] << endl;

    return ;

}

巴特西

CodeForces 311 B Cats Transport 斜率优化DP

最新文章

热门文章