[ 백준 5466, IOI 2009 Day 2 ] 상인 (SalesMan)

문제 링크

https://www.acmicpc.net/problem/5466

https://oj.uz/problem/view/IOI09_salesman

문제 요약

상인이 어떤 마을의 시장에서 다른 마을의 시장으로 가서 이득을 취할려고 한다.

위로 올라갈 때에는 U의 비용이, 아래로 내려갈 때에는 D의 비용이 들고, 각 마을의 위치는 $P_i$,각 마을에서 얻을 수 있는 이득은 $M_i$이다.

각 마을의 시장이 열리는 날은 $D_i$이며, 마지막에 방문한 곳에서 집으로 꼭 와야한다. 집의 좌표는 S이다.

이 때, 상인이 얻을 수 있는 최대 이득은 얼마인가?

간단한 DP( Subtask 1, $N\leq5000$ )

dp[i] : i번째시장까지 얻을 수 있는 상인의 최대 이득

최초엔 상인은 집의 위치에 있고, 마지막엔 항상 집에 있어야 하므로 dp[N+1]까지 정의를 하여서 값을 구하도록 하자.

이렇게 점화식을 세우면 dp[i]는 다음과 같이 정의할 수 있다.

$dp[i]=\begin{equation}{\max\limits_{j=0}^{i-1}}\Big(dp[j]-\big(P_i>P_j ? D : U\big)\times\displaystyle abs(P_i-P_j)\Big)\end{equation}+M_i$

0부터 도는 이유는 상인이 S의 위치에 있기 때문에, dp[0]=S으로 잡고 시작하는 것이 정신건강에 좋기 때문이다.

또한, i번째날로 정하는 것은 정렬을 통해 판정한다.

식의 변형과 아이디어의 도입( Subtask 2, $P_i\neq P_j$ )

여기서, 우리는 식을 약간 변형시켜보자.

$dp[j]-\big(P_i<P_j ? U : D\big)\times\displaystyle abs(P_i-P_j)$ 이식에서, 조금 더 변형을 하기 쉽게 항상 $P_i>P_j$라고 가정을 해보자.

그러면, 위 식은 $dp[j]-D\times\displaystyle (P_i-P_j)$가 되고, 이를 조금 더 풀어쓰면 $dp[j]-D\times P_i+D\times\displaystyle P_j$라고 할 수 있다.

뒤의 $D\times\displaystyle P_i$가 상수가 된다!!

따라서, 우리는 $dp[j]+D\times P_j$의 최대값만 구해내면 된다.

반대로, $P_i<P_j$일 경우엔 $dp[j]-U\times P_j$가 될 것이다.

하지만, 얘가 올라가느냐 내려가느냐에 따라 우리는 곱해주는 값을 자꾸 바꿔줘야 한다. 너무나 불편하다.

따라서, 우리는 간편하게 현재 좌표를 기준으로 위쪽에 있는 시장들과 아래쪽에 있는 시장들을 통한 값을 따로 구해서, 그 두 값 중 최대값을 구해주면 된다.

이렇게 두 가지 subtask로 나눠버리면, 문제는 훨씬 쉬워진다.

그 이유는, 아래로 가는 거에 대한 Segment tree와 위쪽으로 가는거에 대한 Segment tree를 만든 후에, 구간을 계속적으로 처리해주면 되기 때문이다.

값을 갱신할 때에는 위쪽으로 가는 거에 대한 것엔 $D[i]-U\times P_i$를, 아래쪽으로 가는거에 대한 것엔 $D[i]+D\times P_i$를 해준다. 

값을 구할 때에는 세그먼트 트리를 통해 downtree에서는 0과 현재위치까지를, uptree에선 현재위치에서 시장이 열릴 수 있는 최대 위치까지의 쿼리를 구한다.

그 후, 위쪽에서 온거였으면 $+U\times P_i$를, 아래쪽에서 온거였으면 $-D\times P_i$를 하면 된다.

이렇게 하면, Subtask 2가 완료된다.

하나의 새로운 아이디어의 도입 ( Subtask3 )

앞의 아이디어로는 Subtask 3을 처리하지 못한다. 그 이유는, 같은 날에 열리는 시장끼리도 이동이 가능하기 때문이다.

따라서, 우리는 이걸 처리하기 위해선 아예 다른 아이디어를 가져와야 한다.

일단, 같은 날에 열리는 시장의 위치를 정렬하자.

그러면, 시장의 위치는 다음과 같이 된다.

시장에 갔을 때 얻을 수 있는 이득은 항상 0보다 크므로, $a_1\to a_3$이나 $a_1\to a_4$ 등 한 간격이 아니라 여러 간격을 건너뛸 때에는 그 사이에 있는 모든 시장을 들렀다가 가는 것이 이득이다.

따라서, 우리는 한 간격으로 가는걸로 무방하다. 왜냐하면, 시장을 들렸다가 간다는 것의 의미는 $a_1\to a_2$까지 갔다가, $a_2\to a_3$까지 가는거랑 동일하기 때문이다. 만약, $a_1\to a_2$로 갔는데 얘가 다른 날짜의 시장에서 온거보다 손해라면 $a_1\to a_2$에서 가는거보다 그냥 다른 날짜의 시장에서 여기에 도착한 후에, $a_3$로 가는 것이 더 최선이다. 또한, $a_2$에서 $a_1$갔다가 $a_3$가는 것은 최악의 경우임을 알 수 있다.

따라서, 우리는 차례대로 진행하면서 현재 위치가 첫 번째 위치만 아니라면 앞의 위치에서 간거랑 다른 시장에서 온 거랑 비교해서 처리해주면 된다. 물론, 이 경우는 D 쿼리이다.

반대의 경우엔 U 쿼리를 처리해주면 된다.

코드

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500009;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpi;
vpi mark[MAXN];
int n,u,d,s,uptree[2*MAXN],downtree[2*MAXN];
int query(int *arr,int l,int r)
{
    int ans=-INF;
    for(l+=MAXN,r+=MAXN;l<=r;l>>=1,r>>=1)
    {
        if(l&1) ans=max(ans,arr[l++]);
        if(~r&1) ans=max(ans,arr[r--]);
    }
    return ans;
}
void update(int *arr,int x,int v)
{
    x+=MAXN;
    arr[x]=max(arr[x],v);
    for(;x>1;x>>=1) arr[x>>1]=max(arr[x],arr[x^1]);
}
void updatep(int x,int v)
{
    update(uptree,x,v-u*x);
    update(downtree,x,v+d*x);
}
int realquery(int a)
{
    return max(query(downtree,0,a)-d*a,query(uptree,a,MAXN-1)+u*a);
}
void markt(vpi &market)
{
    if(market.size()==0) return;
    sort(market.begin(),market.end());
    vector<int> U,D;
    int sz=market.size();
    for(int i=0;i<sz;i++)
    {
        int temp=realquery(market[i].first);
        U.push_back(temp),D.push_back(temp);
    }
    for(int i=0;i<sz;i++)
    {
        if(i!=0) D[i]=max(D[i],D[i-1]-d*(market[i].first-market[i-1].first));
        D[i]+=market[i].second;
    }
    for(int i=sz-1;i>=0;i--)
    {
        if(i!=sz-1) U[i]=max(U[i],U[i+1]-u*(market[i+1].first-market[i].first));
        U[i]+=market[i].second;
    }
    for(int i=0;i<sz;i++) updatep(market[i].first,max(U[i],D[i]));
}
int main()
{
    scanf("%d %d %d %d",&n,&u,&d,&s);
    for(int i=0,x,y,z;i<n;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        mark[x].push_back(make_pair(y,z));
    }
    memset(uptree,0xc0,sizeof(uptree));
    memset(downtree,0xc0,sizeof(downtree));
    updatep(s,0);
    for(int i=1;i<=500001;i++) markt(mark[i]);
    return !printf("%d",realquery(s));
}

https://oj.uz/submission/56099