본문 바로가기

알고리즘 관련/BOJ

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번째 점에 서 있을 경우

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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;
int h, g, x, y;
int dp[1010][1010][2];
pair<intint> hv[1010];
pair<intint> gv[1010];
int cal(pair<intint> x, pair<intint> 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&&== 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, -1sizeof(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(101));
    return 0;
}
 
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)10815 숫자 카드  (0) 2017.01.03
BOJ)1733 등번호  (2) 2017.01.03
BOJ)14168 Cow Checklist  (0) 2017.01.03
BOJ)11895 속이기  (0) 2017.01.03
BOJ)2401 최대 문자열 붙여넣기  (1) 2016.12.30
BOJ)13168 내일로 여행  (0) 2016.12.30