C++ 解法, 执行用时: 66ms, 内存消耗: 8240K, 提交时间: 2022-06-25 20:28:55

#include<bits/stdc++.h>
using namespace std;
int n,T;
int a[1010];
int l[1010][1010],r[1010][1010];
int main()
{
    cin>>T;
	while(T--)
	{
        cin>>n;
        for(int i=1; i<=n; i++)
            cin>>a[i];
		for(int len=1; len<=n; len++)
		{
			for(int i=1; i+len-1<=n; i++)
			{
				int j=len+i-1;
				int ll=l[i][j-1],rr=r[i][j-1];
				int x=a[j];
				if(len==1)
				l[i][j]=r[i][j]=a[i];
				else{
					if(x==rr)l[i][j]=0;
					else if(x<ll&&x<rr||x>ll&&x>rr)l[i][j]=x;
					else if(ll>rr)l[i][j]=x-1;
					else l[i][j]=x+1;
				}
				ll=l[i+1][j],rr=r[i+1][j],x=a[i];
				if(len==1)l[i][j]=r[i][j]=a[j];
				else{
					if(x==ll)r[i][j]=0;
					else if(x<ll&&x<rr||x>ll&&x>rr)r[i][j]=x;
					else if(ll<rr)r[i][j]=x-1;
					else r[i][j]=x+1; 
				}
			}
		}
		cout<<(l[2][n]!=a[1])<<endl;
	}
    return 0;
}