BOJ)2618 경찰차

문제:icpc.me/2618

경찰차 두대가 사건을 순서대로 처리할 때 가장 적은 거리를 이동하도록 사건을 배치하는 경우와 거리를 출력하는 문제이다.

dp[x][y] = 경찰차 1이 x번째 사건을 경찰차 2가 y번째 사건을 마지막으로 처리하였을 때 이동한 거리의 합의 최솟값으로 정의한 뒤 문제를 해결해주면 된다.

점화식은 dp[x][y] = min(dp[prev][y]+ dist(prev,x) , dp[x][prev] + dist(prev,y))이다.

소스에서는 바텀업 방식으로 구현하여 테이블의 정의가 약간 바뀌었다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 1987654321
using namespace std;
int dp[1001][1001], n, w, back[1001];
pair<int, int> d[1001];
int getdist(pair<int, int> a, pair<int, int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}
int func(int x, int y) {
    if (x == w || y == w)return 0;
    int &ret = dp[x][y];
    if (ret != -1)return ret;
    int fir, sec;
    if (!x) 
        fir = func(max(x, y) + 1, y) + getdist(d[max(x, y) + 1], { 1,1 });
    else 
        fir = func(max(x, y) + 1, y) + getdist(d[max(x, y) + 1], d[x]);
    if (!y)
        sec = func(x, max(x, y) + 1) + getdist(d[max(x, y) + 1], { n,n });
    else
        sec = func(x, max(x, y) + 1) + getdist(d[max(x, y) + 1], d[y]);
    return ret = min(fir, sec);
}
void solve(int x, int y) {
    if (x == w || y == w) return;
    int fir, sec;
    if (!x)
        fir = func(max(x, y) + 1, y) + getdist(d[max(x, y) + 1], { 1,1 });
    else
        fir = func(max(x, y) + 1, y) + getdist(d[max(x, y) + 1], d[x]);
    if (!y)
        sec = func(x, max(x, y) + 1) + getdist(d[max(x, y) + 1], { n,n });
    else
        sec = func(x, max(x, y) + 1) + getdist(d[max(x, y) + 1], d[y]);
    if (fir < sec) {
        back[max(x, y) + 1] = 1;
        solve(max(x, y) + 1, y);
    }
    else {
        back[max(x, y) + 1] = 2;
        solve(x, max(x, y) + 1);
    }
}
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &n, &w);
    for (int i = 1; i <= w; i++)
        scanf("%d%d", &d[i].first, &d[i].second);
    printf("%d\n", func(0, 0));
    solve(0, 0);
    for (int i = 1; i <= w; i++)
        printf("%d\n", back[i]);
    return 0;
}