백준2518 회전 테이블

작성일 | In

문제 링크

  • http://icpc.me/2518

문제 출처

  • 2012 KOI 고등부 3번

사용 알고리즘

  • DP

시간복잡도

  • O(p1 * p2 * p3)

풀이

3명의 사람 모두 정해진 순서대로 각각 최대 100개의 음식 을 먹고 싶어 합니다.

dp[a][b][c][d] = 1번 사람이 a개, 2번 사람이 b개, 3번 사람이 c개를 먹었고, 마지막으로 d번 사람이 먹었을 때 최소 회전
으로 정의를 해서 dp table을 채워주면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int n;
int arr[3][111], sz[3];
int dp[111][111][111][3];
const int inf = 1e9+7;

int cost(int a, int b){
    int d = abs(a - b);
    d %= n;
    return min(d, n-d);
}

int f(int i, int j, int k, int s){
    int &res = dp[i][j][k][s];
    if(res != -1) return res;
    if(i > sz[0] + 1 || j > sz[1] + 1 || k > sz[2] + 1) return res = 1e9;
    if(i == sz[0] + 1 && j == sz[1] + 1 && k == sz[2] + 1) return res = 0;
    int t = 0;
    if(s == 0) t = arr[0][i-1];
    else if(s == 1) t = arr[1][j-1] + n/3*2;
    else t = arr[2][k-1] + n/3;
    res = inf;
    res = min(res, f(i+1, j, k, 0) + cost(t, arr[0][i]));
    res = min(res, f(i, j+1, k, 1) + cost(t, arr[1][j] + n/3*2));
    res = min(res, f(i, j, k+1, 2) + cost(t, arr[2][k] + n/3));
    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i=0; i<3; i++){
        cin >> sz[i];
        for(int j=1; j<=sz[i]; j++){
            cin >> arr[i][j]; arr[i][j]--;
        }
    }
    arr[1][0] = n/3, arr[2][0] = n/3*2;
    memset(dp, -1, sizeof dp);
    cout << f(1, 1, 1, 0);
}