티스토리 뷰

알고리즘 관련/BOJ

BOJ)14590 KUBC League (Small)

JASON 자손9319 2017. 6. 6. 18:08

문제: icpc.me/14590


외판원 문제(TSP)와 유사한 문제이다.


외판원 문제는 비트마스크 DP로 해결할 수 있다.


dp[state][pos] <- 현재까지 커버한 상태를 state로 가지고 현재 pos의 위치에 서 있을 때 선수 나열의 최대 길이


점화식은 for(i: 1~n) if(a[pos][i] && !((1<<i)&state)) =>max(dp[state|(1<<i)][i]+1 이 된다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a[22][22];
int dp[<< 21][21];
int func(int state, int pos) {
    int &ret = dp[state][pos];
    if (ret != -1)return ret;
    ret = 0;
    for (int i = 1; i <= n; i++) {
        if (a[pos][i] && !((<< i)&state)) 
            ret = max(ret, func(state | (<< i), i) + 1);
    }
    return ret;
}
void tracking(int state, int pos) {
    for (int i = 1; i <= n; i++) {
        if (a[pos][i] && !((<< i)&state)) {
            if (dp[state][pos] == dp[state | (<< i)][i] + 1) {
                printf("%d ", i);
                tracking(state | (<< i), i);
                break;
            }
        }
    }
}
int main() {
    scanf("%d"&n);
    memset(dp, -1sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            scanf("%d"&a[i][j]);
    }
    int r = func(<< 11) ;
    printf("%d\n1 ", r + 1);
    int idx = 1;
    tracking(<< 11);
    return 0;
}
cs


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

BOJ)1405 미친 로봇  (0) 2017.06.07
BOJ)10838 트리  (0) 2017.06.07
BOJ)14590 KUBC League (Small)  (0) 2017.06.06
BOJ)13538 XOR 쿼리  (0) 2017.06.05
BOJ)1322 X와K  (0) 2017.06.05
BOJ)1837 암호제작  (2) 2017.06.05
댓글
댓글쓰기 폼