BOJ 10563 정수 게임

BOJ 10563 정수 게임

[분류 : 다이나믹 프로그래밍]

 

  은근히 어려운 문제..

 

[풀이]

  [구간 내의 수 선택] 현재 수를 뽑을 수 있는 구간을 [l, r]이라고 하자. 여기 안에서 조건에 만족하는, 즉 양 옆에 수들 모두 자신보다 작은 후보 집합 S={x | A[x-1] < A[x] > A[x+1]} 중에서 하나 x를 뽑았다고 해보자.

 

  [구간 밖의 선택] 그러면 구간은 [l, x), (x, r] 구간으로 나눠지고, 여기서 어느 구간을 선택할지를 고르면 되는데, 1이 존재하는 구간은 반드시 둘 중에 하나밖에 없다. 그 1이 포함되지 않은 구간을 선택하는 경우는 현재 내가 1이 포함되어 있는 구간 중 어느 수를 선택해도 반드시 질 경우에 유효할 수 있다.
  가령 구간 [l, x)을 뽑으면 반드시 진다고 해보자. 그러면 일부러 다른 구간 (x, r]에 있는 수 하나를 뽑아버리면 그 다음 사람이 [l, x)를 뽑게되면 필승이 되는 방식이다. 이러한 구간 밖의 선택은 홀짝 여부만 판단하면 된다. 두 명 모두 바깥 구간의 수를 뽑는 것은 경우의 수가 중복되기 때문이다.

 

#include<cstdio>
#include<cstring>
const int MAX_N = 100;
int s, dp[MAX_N][MAX_N][2], a[MAX_N];
int rec(int l, int r, int c) {
    int& ret = dp[l][r][c];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = l; !ret && i <= r; i++) if ((i == l || a[i - 1] < a[i]) && (i == r || a[i] > a[i + 1])) {
        if (s == i) return ret = 1;
        if (s < i)
            ret |= !rec(l, i - 1, (c + r - i) % 2);
        else ret |= !rec(i + 1, r, (c + i - l) % 2);
    }
    if (c)
        ret |= !rec(l, r, 0);
    return ret;
}
int main() {
    int T, N, i;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        memset(dp, -1, sizeof dp);
        for (i = 0; i < N; i++) {
            scanf("%d", &a[i]);
            if (a[i] == 1) s = i;
        }
        puts(rec(0, N - 1, 0) ? "Alice" : "Bob");
    }
    return 0;
}