C++14(g++5.4) 解法, 执行用时: 79ms, 内存消耗: 8284K, 提交时间: 2019-09-16 16:53:50

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 1010
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int n,a[MAX],L[MAX][MAX],R[MAX][MAX];
int main()
{
    int T=read();
    while(T--)
    {
        n=read();
        for(int i=1;i<=n;++i)a[i]=read();
        for(int i=1;i<=n;++i)L[i][i]=R[i][i]=a[i];
        for(int len=2;len<=n;++len)
            for(int i=1,j=i+len-1;j<=n;++i,++j)
            {
                int x=a[j],l=L[i][j-1],r=R[i][j-1];
                if(x==r)L[i][j]=0;
                else if((x>l&&x>r)||(x<l&&x<r))L[i][j]=x;
                else if(r<x&&x<l)L[i][j]=x-1;
                else L[i][j]=x+1;
                x=a[i],l=L[i+1][j],r=R[i+1][j];
                if(x==l)R[i][j]=0;
                else if((x>l&&x>r)||(x<l&&x<r))R[i][j]=x;
                else if(r<x&&x<l)R[i][j]=x+1;
                else R[i][j]=x-1;
            }
        puts(a[1]==L[2][n]?"0":"1");
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 88ms, 内存消耗: 8312K, 提交时间: 2020-04-01 17:04:56

#include<stdio.h>
#include<string.h>
int n,a[1005],l[1005][1005],r[1005][1005];
int main()
{
    int T,i,j,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        if(n==1)
        printf("1\n");
        else
        {
            for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
            memset(l,-1,sizeof(l));
            memset(r,-1,sizeof(r));
            for(i=1;i<=n;i++)
            l[i][i]=r[i][i]=a[i];
            for(i=1;i<=n-1;i++)
            {
                for(j=1;j+i<=n;j++)
                {
                    k=j+i;
                    if(r[j][k-1]==a[k]) l[j][k]=0;
                    else if(a[k]<r[j][k-1]&&a[k]<l[j][k-1]||a[k]>r[j][k-1]&&a[k]>l[j][k-1]) l[j][k]=a[k];
                    else if(r[j][k-1]<l[j][k-1]) l[j][k]=a[k]-1;
                    else l[j][k]=a[k]+1;
                    if(l[j+1][k]==a[j]) r[j][k]=0;
                    else if(a[j]<l[j+1][k]&&a[j]<r[j+1][k]||a[j]>l[j+1][k]&&a[j]>r[j+1][k]) r[j][k]=a[j];
                    else if(l[j+1][k]<r[j+1][k]) r[j][k]=a[j]-1;
                    else
                    r[j][k]=a[j]+1;
                }
            }
            if(r[1][n-1]==a[n])
            printf("0\n");
            else
            printf("1\n");
        }
    }
    return 0;
}