Codeforces Round #577 (Div. 2) D. Treasure Hunting （贪心+dp）

题目链接

题意：给定n*m的格子图 ， 某些格子有宝藏 。出发点在最下角(1,1)， 移动规则为：不可以向下走。只有位于某些特殊列的时候能往上走， 否则只能左右移动。

数据范围是2e5 。

分析：首先每一行的宝藏中，我们只需关心最左端和最右端的2个就行，

取完这一行的宝藏后，停的位置要么是在最左端宝藏 记为

L

,要么是在最右端宝藏 记为

R

。

要向上走的时候，L/R每种情况又有2种选择，记

L

右边最近的特殊列为

Lr

,左边最近的特殊列为

Ll

,停在L位置的时候，要么从Lr上去，要么从Ll上去,上去之后停的位置又有最左端/最右端两种情况 。一共是2 * 2 * 2=8种情况 。

设ansr / ansl 为停在最右端/最左端情况下左右移动的最小值。

而且容易看出停在L/R处的状态是没有后效性的。 所以可以用dp进行递推。

最终答案就是

向上移动格数+min(ansr,ansl)

。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn = 2e5+10;
const int mx = 31;
const int mod = 1e9+7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int INF = 1e9+7;
//给定n*m的格子图  某些格子有宝藏 起初在最下角(1,1) 只能位于某些特殊列的时候才能往上走 否则只能左右移动
//问拿完所有宝藏的最小移动次数是多少
//对于每一列 我们只关心最左边/最右边的宝藏 
int n,m,k,q;
ll l[maxn],r[maxn];//第i列的最左端 最右端的宝藏列
vector<ll> safe;//安全列
ll ansl,ansr;//上一次 停在最左端 /最右端的答案  取min  
ll maxa=0;//最大的行数 min(ansl,ansr)+maxa-1 就是最终答案
int main()
{
    cin>>n>>m>>k>>q;
    for(int i=1;i<=n;i++) l[i]=inf,r[i]=0;
    for(int i=1;i<=k;i++) 
    {
        ll a,b;
        scanf("%I64d %I64d",&a,&b);
        l[a]=min(l[a],b);
        r[a]=max(r[a],b);
        maxa=max(maxa,a);
    }
    for(int i=1;i<=q;i++) 
    {
        ll t;scanf("%I64d",&t);
        safe.push_back(t);
    }
    sort(safe.begin(),safe.end());
    //L R记录上一次的最左端/最右端 因为有的行没用宝藏 所以不能直接用上一行的数据
    if(!r[1]) r[1]=1,l[1]=1;//如果第一行没有宝藏 那么就把起始格子视为宝藏
    int L=l[1],R=r[1];
    ansl=r[1]-1+r[1]-l[1];
    ansr=r[1]-1;
    for(int i=2;i<=n;i++)
    {
        if(!r[i]) continue;
        ll Lr=inf,Ll=inf,Rl=inf,Rr=inf;
        //L的右/左边最近的安全列  R的左/右边最近的安全列  4种情况 每种都有停在L/R两种选择 一共8种  取min
        int indexl=lower_bound(safe.begin(),safe.end(),L)-safe.begin();//L列 右边最近的安全列
        if(indexl>0) Ll=safe[indexl-1];
        if(indexl<q) Lr=safe[indexl];
        int indexr=lower_bound(safe.begin(),safe.end(),R)-safe.begin();//R列 右边最近的安全列
        if(indexr<q) Rr=safe[indexr];
        if(indexr>0) Rl=safe[indexr-1];
        ll nowl=inf,nowr=inf;//拿完本层宝藏的答案

        nowl=min(nowl,ansl+abs(Lr-L)+abs(r[i]-Lr)+abs(l[i]-r[i]));//L->Lr->r[i]->l[i]
        nowl=min(nowl,ansl+abs(Ll-L)+abs(r[i]-Ll)+abs(l[i]-r[i]));//L->Ll->r[i]->l[i]
        nowl=min(nowl,ansr+abs(Rl-R)+abs(r[i]-Rl)+abs(l[i]-r[i]));//R->Rl->r[i]->l[i]
        nowl=min(nowl,ansr+abs(Rr-R)+abs(r[i]-Rr)+abs(l[i]-r[i]));//R->Rr->r[i]->l[i]

        nowr=min(nowr,ansl+abs(L-Lr)+abs(l[i]-Lr)+abs(l[i]-r[i]));//L->Lr-l[i]->r[i]
        nowr=min(nowr,ansl+abs(L-Ll)+abs(l[i]-Ll)+abs(l[i]-r[i]));//L->Ll-l[i]->r[i]
        nowr=min(nowr,ansr+abs(R-Rr)+abs(l[i]-Rr)+abs(l[i]-r[i]));//R->Rr-l[i]->r[i]
        nowr=min(nowr,ansr+abs(R-Rl)+abs(l[i]-Rl)+abs(l[i]-r[i]));//R->Rl-l[i]->r[i]

        ansl=nowl,ansr=nowr;
        L=l[i],R=r[i];
    }
    cout<<min(ansr,ansl)+maxa-1;
    return 0;
}