티스토리 뷰

알고리즘 관련/BOJ

BOJ)9023 연습시즌

JASON 자손9319 2017. 6. 22. 15:52

문제: icpc.me/9023


연습 일정에 맞춰서 경기장이나 호텔을 빌려야 할 때 두 팀이 지불해야하는 비용의 합의 최솟값을 구하는 문제이다.


다이나믹 프로그래밍을 이용하여 해결해줄 수 있는데 점화식을 세울 때 주의할 점은 두 팀 다 쉬는날이 없게해야한다. (무조건 손해) 


dp테이블을 dp[x][y][bx][by] (x번째 경기 y번째 경기를 진행해야되고 bx,by는 이전에 호텔에 묶었는지 여부 )로 세워준다음에 점화식을 세워주면 된다.


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
43
44
45
46
47
48
49
50
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define INF 1e9
using namespace std;
int t, c, d, e, z, dp[110][110][2][2];
vector<int> a, b;
int func(int x, int y, int bx, int by) {
    if (x == a.size() && y == b.size())return 0;
    int &ret = dp[x][y][bx][by];
    if (ret != -1)return ret;
    ret = INF;
    if (x < a.size() && y < b.size())
        ret = min(ret, func(x + 1, y + 100+ ((a[x] == b[y]) ? c : * c));
    if (y < b.size()) {
        if (bx)
            ret = min(ret, func(x, y + 110+ e + c);
        else
            ret = min(ret, func(x, y + 110+ d + e + c);
    }
    if (x < a.size()) {
        if (by)
            ret = min(ret, func(x + 1, y, 01+ e + c);
        else
            ret = min(ret, func(x + 1, y, 01+ d + e + c);
    }
    return ret;
}
int main() {
    scanf("%d"&t);
    while (t--) {
        memset(dp, -1sizeof(dp));
        scanf("%d%d%d"&c, &d, &e);
        a.clear();
        b.clear();
        while (1) {
            scanf("%d"&z);
            if (!z)break;
            a.push_back(z);
        }
        while (1) {
            scanf("%d"&z);
            if (!z)break;
            b.push_back(z);
        }
        printf("%d\n", func(0000));
    }
    return 0;
}
cs


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

BOJ)8872 빌라봉  (0) 2017.07.08
BOJ)1444 숌 언어  (0) 2017.07.05
BOJ)9023 연습시즌  (0) 2017.06.22
BOJ)13309 트리  (1) 2017.06.21
BOJ)2507 공주 구하기  (0) 2017.06.18
BOJ)12869 뮤탈리스크  (0) 2017.06.18
댓글
댓글쓰기 폼