2618번: 경찰차

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

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_W = 1e3;
int n, w, dp[MAX_W + 1][MAX_W + 1], fx[MAX_W + 1][MAX_W + 1], fy[MAX_W + 1][MAX_W + 1], x[MAX_W + 1], y[MAX_W + 1];
void f(int x, int y) {
    if (fx[x][y] == -1 || fy[x][y] == -1) {
        puts(fx[x][y] == -1 ? "1" : "2");
        return;
    }
    f(fx[x][y], fy[x][y]);
    puts(x == fx[x][y] ? "2" : "1");
}
int main() {
    scanf("%d %d", &n, &w);
    for (int i = 1; i <= w; i++) scanf("%d %d", x + i, y + i);
    for (int i = 0; i <= w; i++) {
        for (int j = 0; j <= w; j++) {
            dp[i][j] = 1e9;
            if (i < j) {
                if (j == 1)dp[0][1] = abs(n - x[1]) + abs(n - y[1]), fy[i][j] = -1;
                else if (i + 1 == j) {
                    for (int k = 0, t; k < i; k++) {
                        t = k ? dp[i][k] + abs(x[k] - x[j]) + abs(y[k] - y[j])
                            : dp[i][k] + abs(n - x[j]) + abs(n - y[j]);
                        if (dp[i][j] > t) dp[i][j] = t, fx[i][j] = i, fy[i][j] = k;
                    }
                }
                else {
                    dp[i][j] = dp[i][j - 1] + abs(x[j] - x[j - 1]) + abs(y[j] - y[j - 1]);
                    fx[i][j] = i;
                    fy[i][j] = j - 1;
                }
            }
            if (i>j) {
                if (i == 1) dp[1][0] = abs(1 - x[1]) + abs(1 - y[1]), fx[i][j] = -1;
                else if (i == j + 1) {
                    for (int k = 0, t; k < j; k++) {
                        t = k ? dp[k][j] + abs(x[k] - x[i]) + abs(y[k] - y[i])
                            : dp[k][j] + abs(1 - x[i]) + abs(1 - y[i]);
                        if (dp[i][j] > t) dp[i][j] = t, fx[i][j] = k, fy[i][j] = j;
                    }
                }
                else {
                    dp[i][j] = dp[i - 1][j] + abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);
                    fx[i][j] = i - 1;
                    fy[i][j] = j;
                }
            }
        }
    }
    int r = 1e9, tx, ty;
    for (int i = 0; i <w; i++) {
        if (dp[i][w] < r)r = dp[i][w], tx = i, ty = w;
        if (dp[w][i] < r) r = dp[w][i], tx = w, ty = i;
    }
    printf("%d\n", r);
    f(tx, ty);
    return 0;
}