52 lines
1.6 KiB
C++
52 lines
1.6 KiB
C++
#include <cstdio>
|
||
|
||
using namespace std;
|
||
const int N = 1010;
|
||
int n;
|
||
int a[N];
|
||
int left[N][N], right[N][N]; // left,right 在 iostream库中用过了，不能用！
|
||
|
||
int main() {
|
||
int T;
|
||
scanf("%d", &T);
|
||
while (T--) {
|
||
scanf("%d", &n);
|
||
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
|
||
|
||
for (int len = 1; len <= n; len++) // 枚举长度
|
||
for (int i = 1; i + len - 1 <= n; i++) { // left[i][j],从i到j
|
||
int j = i + len - 1;
|
||
if (len == 1)
|
||
left[i][j] = right[i][j] = a[i]; // DP初始值
|
||
else {
|
||
int L = left[i][j - 1], R = right[i][j - 1], X = a[j];
|
||
if (R == X)
|
||
left[i][j] = 0;
|
||
else if (X < L && X < R || X > L && X > R)
|
||
left[i][j] = X;
|
||
else if (L > R)
|
||
left[i][j] = X - 1;
|
||
else
|
||
left[i][j] = X + 1;
|
||
|
||
L = left[i + 1][j], R = right[i + 1][j], X = a[i];
|
||
if (L == X)
|
||
right[i][j] = 0;
|
||
else if (X < L && X < R || X > L && X > R)
|
||
right[i][j] = X;
|
||
else if (R > L)
|
||
right[i][j] = X - 1;
|
||
else
|
||
right[i][j] = X + 1;
|
||
}
|
||
}
|
||
|
||
if (n == 1)
|
||
puts("1");
|
||
else
|
||
printf("%d\n", left[2][n] != a[1]);
|
||
}
|
||
|
||
return 0;
|
||
}
|