记录编号	401690	评测结果	AAAAAAAAAA
题目名称	2675.[ZJOI 2009]取石子游戏	最终得分	100
用户昵称	阿十三	是否通过	通过
代码语言	C++	运行时间	0.189 s
提交时间	2017-05-03 17:37:05	内存使用	31.81 MiB

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
template<typename T> inline bool chkmin(T &a, const T &b)
{
    return a > b ? a = b, 1 : 0;
}
template<typename T> inline bool chkmax(T &a, const T &b)
{
    return a < b ? a = b, 1 : 0;
}
int left[2010][2100],right[2010][2010];
int a[2010];

void rd(int &x)
{
    x=0;
    int ch=getchar();
    while(ch<'0'||'9'<ch) ch=getchar();
    while('0'<=ch&&ch<='9') x=x*10+ch-'0', ch=getchar();
}

int main()
{
    //freopen("E:/creat/in11_test.in","r",stdin);
    //freopen("E:/creat/in11_test.out","w",stdout);
    freopen("zjoi09stone.in", "r", stdin);
	freopen("zjoi09stone.out", "w", stdout);
    int ca;
    scanf("%d",&ca);
    while(ca--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            left[i][i]=right[i][i]=a[i];
        }
        REP(k,1,n)
        {
            for(int i=1; i+k<=n; i++)
            {
                int j=i+k,L,R,z;
                L=left[i][j-1],R = right[i][j - 1], z = a[j];
                if(R==z)
                    left[i][j]=0;
                else if(L > z && R > z) left[i][j] = z;
                else if(L <= z && R > z) left[i][j] = z + 1;
                else if(L > z && R < z) left[i][j] = z - 1;
                else left[i][j]=z;
                L = left[i + 1][j], R = right[i + 1][j], z = a[i];
                if(R == z) right[i][j] = 0;
                else if(L > z && R > z) right[i][j] = z;
                else if(L <= z && R > z) right[i][j] = z + 1;
                else if(L > z && R < z) right[i][j] = z - 1;
                else right[i][j] = z;
            }
        }
        if(a[1]==left[2][n]) printf("0\n");
        else printf("1\n");
    }
    return 0;
}