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;
}