Mice and Holes 单调队列优化dp

n个老鼠，m个洞，告诉你他们的一维坐标和m个洞的容量限制，问最小总距离。1 ≤ n, m ≤ 5000。

首先列出朴素的dp方程：\(f[i][j]=min(f[i-1][k]+s[j]-s[k])\)，其中\(f[i][j]\)表示前i个洞，有j个老鼠进洞。s[j]-s[k]表示第k+1到j个老鼠进洞的路径和。然后我们发现，\(f[i][j]\)的值取决于最小的\(f[i-1][k]-s[k]\ (k<=j)\)，同时，j-k必须小于等于第i个洞的容量。于是我们建一个单调队列，队列存储最优的k。然后如果\(j-q[head]\)大于第i个洞的容量，那么head++，然后如果\(f[i-1][j]\)大于队列末尾，那么就一直tail--。这样就可以把\(O(n^3)\)的时间复杂度优化成O(n^2)。

对了，初始化的时候要注意，想清楚没有优化的时候是什么样的状态。其实不难的。

#include <cstdio>

#include <cstring>

#include <algorithm>

typedef long long LL;

const LL maxn=5005, INF=1e18;

inline LL abs(LL x){ return x<0?-x:x; }

struct Hole{

    LL pos, cap;

    void set(LL x, LL y){ pos=x; cap=y; }

}hole[maxn];

bool cmp(const Hole &a, const Hole &b){

    return a.pos<b.pos; }

//queue：当前第i个洞里面关于有几个老鼠的单调队列

LL n, m, head, tail, queue[maxn];

LL mice[maxn], pre[maxn];

LL fpre[maxn], fnow[maxn], s[maxn];

int main(){

    scanf("%lld%lld", &n, &m);

    for (LL i=1; i<=n; ++i)

        scanf("%lld", &mice[i]);

    std::sort(mice+1, mice+n+1);

    for (LL i=1; i<=m; ++i)

        scanf("%lld%lld", &hole[i].pos, &hole[i].cap);

    std::sort(hole+1, hole+m+1, cmp);

    //pre:洞最多可容纳老鼠的前缀和

    pre[1]=hole[1].cap;

    for (LL i=2; i<=m; ++i)

        pre[i]=pre[i-1]+hole[i].cap;

    if (pre[m]<n){

        printf("-1\n");

        return 0;

    }

    fpre[0]=fnow[0]=0;

    for (int j=1; j<=n; ++j)

        fpre[j]=fnow[j]=INF;

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

        //si:前i个老鼠都放在此洞中的代价

        s[0]=0;

        for (LL j=1; j<=n; ++j)

            s[j]=s[j-1]+abs(hole[i].pos-mice[j]);

        head=0; tail=0;

        for (LL j=0; j<=n; ++j){

            //放不进去，那显然是直接跳过

            if (j>pre[i]) break;

            //不能让这个洞容纳更多老鼠

            while (head<tail&&j-queue[head]>hole[i].cap) ++head;

            //单调队列，不是min的通通吃掉

            while (head<tail&&fpre[j]-s[j]<=

                   fpre[queue[tail-1]]-s[queue[tail-1]]) --tail;

            queue[tail++]=j;

            fnow[j]=fpre[queue[head]]+s[j]-s[queue[head]];

        }

        for (LL j=0; j<=n; ++j)

            fpre[j]=fnow[j];

    }

    printf("%lld", fnow[n]);

}

巴特西

Mice and Holes 单调队列优化dp

Mice and Holes 单调队列优化dp

最新文章

热门文章