본문 바로가기

알고리즘 관련/BOJ

BOJ)15270 친구 팰린드롬

문제: icpc.me/15270


명시 된 N의 범위가 작으므로 상태DP를 이용하여 해결할 수 있다.

dp[state][pos] = state(이미 친구가 된 사람들의 상태를 표현)이고 pos번째 까지 친구 관계를 봤을 때 춤을 추는 인원의 최댓값

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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[<< 21][51];
int n, m;
pair<intint> a[51];
int func(int state, int pos) {
    if (pos == m)return 0;
    int &ret = dp[state][pos];
    if (ret != -1)return ret;
    int x = a[pos].first;
    int y = a[pos].second;
    if (!((<< x)&state) && !((<< y)&state)) {
        ret = max(ret, func(state | (<< x) | (<< y), pos + 1+ 2);
    }
    return ret = max(ret, func(state, pos + 1));
}
int main() {
    scanf("%d%d"&n, &m);
    for (int i = 0; i < m; i++
        scanf("%d%d"&a[i].first, &a[i].second);
    memset(dp, -1sizeof(dp));
    int res = func(00);
    if (res != n)res++;
    printf("%d\n", res);
    return 0;
}
cs


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

BOJ)14950 정복자  (0) 2017.12.12
BOJ)15271 친구 팰린드롬2  (0) 2017.12.05
BOJ)14939 불 끄기  (0) 2017.12.04
BOJ)14938 서강그라운드  (0) 2017.12.04
BOJ)14936 엘리베이터 장난  (0) 2017.12.04