-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path10563.cpp
More file actions
54 lines (41 loc) ยท 1.39 KB
/
10563.cpp
File metadata and controls
54 lines (41 loc) ยท 1.39 KB
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
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;
const int MAX = 100;
int T, N, state[MAX + 2], a;
int dp[MAX + 1][MAX + 1][2];
int cal (int s, int e, int remainChk) {
if (dp[s][e][remainChk] != -1) return dp[s][e][remainChk];
if (s == e) return dp[s][e][remainChk] = 1;
int ret = 0;
for (int m = s; m <= e; m++) {
if (state[m - 1] < state[m] && state[m] > state[m + 1]) {
int temp = state[m];
state[m] = 0;
if (a <= m - 1) ret |= (1 - cal(s, m - 1, (remainChk + e - m) % 2));
else ret |= (1 - cal(m + 1, e, (remainChk + m - s) % 2));
state[m] = temp;
}
}
// remainChk = 0์ธ ๊ฒฝ์ฐ => ์ต์ข
์ ์ผ๋ก ๋จ์์๋ ๊ฒ 0๊ฐ์ธ ๊ฒฝ์ฐ์ ๊ฐ์์ง
if (remainChk == 1) ret |= (1 - cal(s, e, 0));
return dp[s][e][remainChk] = ret;
}
int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> T;
while (T--) {
cin >> N;
state[0] = 0;
for (int i = 1; i <= N; i++) {
cin >> state[i];
if (state[i] == 1) a = i;
}
state[N + 1] = 0;
for (int i = 1; i <= MAX; i++) {
for (int j = 1; j <= MAX; j++) {
for (int k = 0; k < 2; k++) dp[i][j][k] = -1;
}
}
cout << (cal(1, N, 0) == 1 ? "Alice" : "Bob") << "\n";
}
return 0;
}