Codeforces 1201D. Treasure Hunting

传送门

看一眼感觉就是 $dp$，但是似乎状态太多了

考虑推推性质

首先每到一行都要把所有宝藏都走到，那么一定会走到最左边的和最右边的宝藏

注意到一旦走完所有宝藏时肯定是在最左边或者最右边的宝藏位置

并且此时要往上走，显然是选择左边或右边的最近的路上去，因为如果选择更远的路上去还不如先上去再走到更远的那个位置

所以发现，我们每一层上去只有四种选择：最左边宝藏的左右两个最近的上去，最右边宝藏的左右两个最近的上去

直接预处理一下每一层的这四个位置然后标号 $0,1,2,3$

那么就可以安心 $dp$ 了，直接设 $f[i][4]$ 表示到了第 $i$ 层并把第 $i$ 层的宝藏走完，此时准备到更上一层的位置为第 $0/1/2/3$

把一层走完直接按先到最左边或者先到最右边分类讨论一下即可

要注意我们一旦把最高的存在宝藏的一层走完即可结束，并且不用准备到更上一层，所以最后一层的转移到特殊处理一下

细节挺多的要仔细点

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=4e5+;

const ll INF=1e18;

ll n,m,K,Q,b[N],L[N],R[N];

ll pre[N],nxt[N],pos[N][];

ll f[N][];

inline ll calc(ll s,ll t,int i)

{

    if(s<||s>m||t<||t>m) return INF;//

    if(!R[i]) return abs(s-t);//

    return min( abs(s-L[i])+abs(L[i]-R[i])+abs(R[i]-t) , abs(s-R[i])+abs(L[i]-R[i])+abs(L[i]-t) );

}

int main()

{

    n=read(),m=read(),K=read(),Q=read();

    ll x,y; memset(L,0x3f,sizeof(L));

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

    {

        x=read(),y=read();

        L[x]=min(L[x],y); R[x]=max(R[x],y);

    }

    for(int i=;i<=Q;i++) b[i]=read();

    int l=,r=; sort(b+,b+Q+); b[Q+]=m+;

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

    {

        while(b[l+]<=i) l++;

        while(b[r]<i) r++;

        pre[i]=b[l]; nxt[i]=b[r];

    }

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

    {

        if(L[i]<=m) pos[i][]=pre[L[i]],pos[i][]=nxt[L[i]];

        if(R[i]>=) pos[i][]=pre[R[i]],pos[i][]=nxt[R[i]];

    }

    memset(f,0x3f,sizeof(f));

    int pre=,prre=;

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

        if(R[pre]) f[pre][i]=calc(,pos[pre][i],pre);

        else f[pre][i]=nxt[]-,pos[pre][i]=nxt[];//

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

    {

        if(!R[i]) continue;

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

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

                f[i][j]=min(f[i][j],f[pre][k]+calc(pos[pre][k],pos[i][j],i)+(i-pre));

        prre=pre; pre=i;

    }

    ll Ans=INF;

    if(!prre) { printf("%lld\n",R[pre]-); return ; }//

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

        Ans=min(Ans, f[prre][k]+(pre-prre)+ min(abs(pos[prre][k]-L[pre]),abs(pos[prre][k]-R[pre])) +(R[pre]-L[pre]) );//

    printf("%lld\n",Ans);

    return ;

}

巴特西

Codeforces 1201D. Treasure Hunting

最新文章

热门文章