BOJ)14168 Cow Checklist

문제:icpc.me/14168

H의 순서와 G의 순서를 지키면서 순서대로 순회 할 때 소모되는 에너지의 최솟값을 구하는 문제이다.

이때 조건이 반드시 시작과 끝은 H의 처음과 끝이어야 한다는거다.

H순서와 G순서를 각각 배열에 저장 한 뒤 다이나믹 프로그래밍을 통하여 문제를 해결하였다.

dp[h][g][s]의 정의는 H순서를 h까지 G순서를 g까지 처리하고 s가 1이면 H의 h번째 점에 서 있을 경우 s가 0이면 G의 g번째 점에 서 있을 경우

앞으로 순회하는데 소모되는 에너지의 최솟값이다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int h, g, x, y;
int dp[1010][1010][2];
pair<int, int> hv[1010];
pair<int, int> gv[1010];
int cal(pair<int, int> x, pair<int, int> y) {
    return (x.first - y.first)*(x.first - y.first) + (x.second - y.second)*(x.second - y.second);
}
int func(int a, int b, int s) {
    if (a == h&&b == g) {
        if (s)return 0;
        else return INF;
    }
    if (a > h)return INF;
    if (b > g)return INF;
    int &ret = dp[a][b][s];
    if (ret != -1)return ret;
    if (s)
        ret = min(func(a + 1, b, s) + cal(hv[a], hv[a + 1]), func(a, b + 1, s ^ 1) + cal(hv[a], gv[b + 1]));
    else
        ret = min(func(a + 1, b, s ^ 1) + cal(gv[b], hv[a + 1]), func(a, b + 1, s) + cal(gv[b], gv[b + 1]));
    return ret;
}
int main() {
    scanf("%d%d", &h, &g);
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= h; i++) {
        scanf("%d%d", &x, &y);
        hv[i] = { x,y };
    }
    for (int i = 1; i <= g; i++) {
        scanf("%d%d", &x, &y);
        gv[i] = { x,y };
    }
    printf("%d\n", func(1, 0, 1));
    return 0;
}