boj2618 경찰차

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

2618번: 경찰차

 

기존 생각은 하루종일

d[w][2] 로 잡고
d[5][0] = 5번째에 0번경찰차가 갔을때 최소 확률
= d[4][0] + (arr[5]-arr[4])
d[3][0] + ????????????? // d[4][1] + ???????????????????? => 여기서 막혔었다.

 

 

하지만 

d[w][w] 로 잡으면 답을 도출할 수 있다.

즉, d[3][4] == 1번 경찰차가 3번까지 처리하고 2번 경찰차가 4번까지 처리했을때의 값이다.

 

 

여기서 또 주의할 것은

d[3][5] 와 d[3][4] 일때의 처리방법이 다르다. 이것은 스스로 고민하자.

그리고 역추적은 쉬우니깐 패스한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define INF 2000000001
#define pii pair<int, int>
using namespace std;
 
 
int n,w;
int d[1001][1001];
pii before[1001][1001];
pii arr[1001];
 
 
int get_dist(int a, int b)
{
    if (a == 0) // n,n
        return  abs(n - arr[b].first) + abs(n - arr[b].second);
    else if(b == 0)
        return abs(arr[a].first - 1) + abs(arr[a].second - 1);
    else
        return abs(arr[a].first - arr[b].first) + abs(arr[a].second - arr[b].second);
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n >> w;
 
    for (int i = 0; i <= w; i++)
    {
        for (int j = 0; j <= w; j++)
            d[i][j] = INF;
    }
 
    
    for (int i = 1; i <= w; i++)
    {
        cin >> arr[i].first >> arr[i].second;
    }
 
    d[0][1] = (n - arr[1].first) + (n - arr[1].second);
    d[1][0] = (arr[1].first - 1) + (arr[1].second - 1);
    for (int i = 2; i <= w; i++)
    {
        d[0][i] = d[0][i - 1] + get_dist(i, i - 1);
        before[0][i] = { 0, i - 1 };
        d[i][0] = d[i-1][0] + get_dist(i, i - 1);
        before[i][0] = { i-1, 0 };
    }
    
 
    for (int i = 1; i <= w; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if (i == j)
                continue;
            else if (i - j == 1) // 5 4  면 3 4 2 4 1 4 0 4
            {
                for (int k = 0; k <= i - 1; k++)
                {
                    int t = d[k][j] + get_dist(i, k);  // 뒤의 k 가 0이라는 것은 앞 경찰차가 0 ~ i까지라는 것이다. 
                    if (d[i][j] > t)                   // 앞의 k가 0이라는 것은 뒤 경찰차가 0~ i 까지라는 것이다.
                    {
                        d[i][j] = t;
                        before[i][j] = { k, j };
                    }
                
                }
            }
            else if (j - i == 1) // 4 5 면
            {
                for (int k = 0; k <= j - 1; k++)
                {
                    int t = d[i][k] + get_dist(k, j);
                    if (d[i][j] > t)
                    {
                        d[i][j] = t;
                        before[i][j] = { i, k };
                    }
                }
                
            }
            else if (i > j)
            {
                d[i][j] = d[i - 1][j] + get_dist(i - 1, i);
                before[i][j] = { i - 1, j };
            }
            else
            {
                d[i][j] = d[i][j - 1] + get_dist(j-1, j);
                before[i][j] = { i, j-1 };
            }
        }
    }
 
    int ans = INF;
    pii p_start;
    int s[1001];
    int s_size = 0;
    for (int i = 0; i < w; i++)
    {
        if (ans > d[i][w])
        {
            ans = d[i][w];
            p_start = { i,w };
        }
        if (ans > d[w][i])
        {
            ans = d[w][i];
            p_start = { w, i };
        }
    }
    
    while (1)
    {
        if (p_start.first == 0 && p_start.second == 0)
            break;
 
        if (p_start.first > p_start.second)
            s[s_size++] = 1;
        else
            s[s_size++] = 2;
 
        p_start = before[p_start.first][p_start.second];
    }
 
    
    cout << ans << '\n';
    for (int i = s_size-1; i >= 0; i--)
        cout << s[i] << '\n';
 
 
}