看一眼感觉就是 $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=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=4e5+7; const ll INF=1e18; ll n,m,K,Q,b[N],L[N],R[N]; ll pre[N],nxt[N],pos[N][4]; ll f[N][4]; inline ll calc(ll s,ll t,int i) { if(s<1||s>m||t<1||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=1;i<=K;i++) { x=read(),y=read(); L[x]=min(L[x],y); R[x]=max(R[x],y); } for(int i=1;i<=Q;i++) b[i]=read(); int l=0,r=1; sort(b+1,b+Q+1); b[Q+1]=m+1; for(int i=1;i<=m;i++) { while(b[l+1]<=i) l++; while(b[r]<i) r++; pre[i]=b[l]; nxt[i]=b[r]; } for(int i=1;i<=n;i++) { if(L[i]<=m) pos[i][0]=pre[L[i]],pos[i][1]=nxt[L[i]]; if(R[i]>=1) pos[i][2]=pre[R[i]],pos[i][3]=nxt[R[i]]; } memset(f,0x3f,sizeof(f)); int pre=1,prre=0; for(int i=0;i<4;i++) if(R[pre]) f[pre][i]=calc(1,pos[pre][i],pre); else f[pre][i]=nxt[1]-1,pos[pre][i]=nxt[1];// for(int i=pre+1;i<=n;i++) { if(!R[i]) continue; for(int j=0;j<4;j++) for(int k=0;k<4;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]-1); return 0; }// for(int k=0;k<4;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 0; }
Codeforces 1201D. Treasure Hunting
原文：https://www.cnblogs.com/LLTYYC/p/11597504.html