티스토리 뷰

알고리즘 관련/BOJ

BOJ)14168 Cow Checklist

JASON 자손9319 2017. 1. 3. 02:49

문제: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
댓글
댓글쓰기 폼