BOJ)9023 연습시즌

문제: icpc.me/9023

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

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

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

#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 + 1, 0, 0) + ((a[x] == b[y]) ? c : 2 * c));
    if (y < b.size()) {
        if (bx)
            ret = min(ret, func(x, y + 1, 1, 0) + e + c);
        else
            ret = min(ret, func(x, y + 1, 1, 0) + d + e + c);
    }
    if (x < a.size()) {
        if (by)
            ret = min(ret, func(x + 1, y, 0, 1) + e + c);
        else
            ret = min(ret, func(x + 1, y, 0, 1) + d + e + c);
    }
    return ret;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        memset(dp, -1, sizeof(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(0, 0, 0, 0));
    }
    return 0;
}