题目地址：洛谷：【P2599】[ZJOI2009]取石子游戏 – 洛谷、BZOJ：Problem 1413. — [ZJOI2009]取石子游戏

题目描述

在研究过Nim游戏及各种变种之后，Orez又发现了一种全新的取石子游戏，这个游戏是这样的： 有n堆石子，将这n堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。 Orez问：对于任意给出一个初始一个局面，是否存在先手必胜策略。

输入输出格式

输入格式：
文件的第一行为一个整数T，表示有 T组测试数据。对于每组测试数据，第一行为一个整数n，表示有n堆石子；第二行为n个整数ai，依次表示每堆石子的数目。

输出格式：
对于每组测试数据仅输出一个整数0或1。其中1表示有先手必胜策略，0表示没有。

输入输出样例

输入样例#1：

1
4
3 1 9 4

输出样例#1：

0

说明

数据范围
对于30%的数据 n≤5 ai≤10^5
对于100%的数据 T≤10 n≤1000 每堆的石子数目≤10^9

题解

我并不能保证底下的题解完全正确，欢迎各位同学阅读的时候自己想一想找找错，毕竟我在想这个题的时候也被绕进去了。包括底下的这个参考资料，我觉得也都有点问题。
参考资料：题解 P2599 【[ZJOI2009]取石子游戏】 – Jason_Yvan 的博客 – 洛谷博客
这里有一种做法，定义lft[i][j]表示(i, j)区间的左边加一堆该数量的石子先手必败，rgt[i][j]表示(i, j)区间的右边加一堆该数量的石子先手必败，我们利用这两个数组的递推关系进行区间DP，来判定每个局面的状况。这是由于局面之间是可以相互转移的。
设计这个定义的合法性基于对于一个区间，lft和rgt的值是唯一确定的。下面给出证明：

1. 若存在不止一个lft值，那么一步可以把一种值拿成另一种值，会发现必败方发生变化，这与我们的定义不符；
2. 若不存在lft值，那么必胜态只可能通过拿右边的石子转移到某个必败态，左边的石子对该状态没有影响。若固定右边的石子数，该状态对应了多种必败态，且左边的石子数都不相同，这相当于存在不止一种lft值，与1矛盾。

首先，类似Nim游戏，我们会发现当只有两堆石子且数量相等的时候，先手必败。因此初始值即lft[i][i] = rgt[i][i] = a[i]。
剩下的是一个区间DP的思路，我们枚举每个区间，进行转移。转移可以对状况分类讨论。
先分析求lft[i][j]，令L = lft[i][j – 1]，R = rgt[i][j – 1]，X = a[j]：

1. R == X：此时区间[i, j]已是必败态，因此lft[i][j] = 0即可；
2. X < L && X < R：lft[i][j] = X。对于左右两堆石子，后手可以按照先手的操作在另外一堆进行同样的操作，直至两堆都没有了。此时会转移至区间[i, j – 1]的状态，该状态又会是分类讨论中的某一种情况，从而走向必败态；
3. X < L && X > R：lft[i][j] = X – 1。如果先手在左边拿到Y，Y < R时，后手右边也可以拿到Y，则变为情况2；Y ≥ R时，后手在右边拿到Y + 1，则又是情况3。如果先手在右边拿到Y，Y < R时，也可到情况2；Y = R时，后手将左边一堆拿完，进入情况1；Y > R时，后手在左边拿到Y – 1，又是情况3；
4. X ≥ L && X < R：lft[i][j] = X + 1。类似情况3的分析即可。
5. X > L && X > R：lft[i][j] = X。先手若将某一堆拿到Y，Y > max(L, R)时，后手跟着先手拿又是情况5；若左侧拿到L或右侧拿到R，则把另一堆拿完，到情况1；否则我们可以设法转移到情况3和4。

rgt[i][j]仍可以用类似的方法来求。令L = lft[i + 1][j]，R = rgt[i + 1][j]，X = a[i]：

1. L == X：此时区间[i, j]已是必败态，因此rgt[i][j] = 0即可；
2. X < R && X < L：rgt[i][j] = X。对于左右两堆石子，后手可以按照先手的操作在另外一堆进行同样的操作，直至两堆都没有了。此时会转移至区间[i + 1, j]的状态，该状态又会是分类讨论中的某一种情况，从而走向必败态；
3. X < R && X > L：rgt[i][j] = X + 1。如果先手在右边拿到Y，Y < L时，后手左边也可以拿到Y，则变为情况2；Y ≥ L时，后手在左边拿到Y – 1，则又是情况3。如果先手在左边拿到Y，Y < L时，也可到情况2；Y = L时，后手将右边一堆拿完，进入情况1；Y > L时，后手在右边拿到Y + 1，又是情况3；
4. X ≥ R && X < L：rgt[i][j] = X – 1。类似情况3的分析即可。
5. X > R && X > L：rgt[i][j] = X。先手若将某一堆拿到Y，Y > max(L, R)时，后手跟着先手拿又是情况5；若左侧拿到L或右侧拿到R，则把另一堆拿完，到情况1；否则我们可以设法转移到情况3和4。

最后验证a[1]是否与lft[2][n]相等即可。复杂度O(Tn^2)。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 1005;

int T, n, a[MAXN], lft[MAXN][MAXN], rgt[MAXN][MAXN];

int main() {
    T = readint();
    while(T--) {
        n = readint();
        for(int i = 1; i <= n; i++) {
            a[i] = lft[i][i] = rgt[i][i] = readint();
        }
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i + k <= n; i++) {
                int j = i + k, L = lft[i][j - 1], R = rgt[i][j - 1], X = a[j];
                if(R == X) lft[i][j] = 0;
                else if(L > X && R > X) lft[i][j] = X;
                else if(L <= X && R > X) lft[i][j] = X + 1;
                else if(L > X && R < X) lft[i][j] = X - 1;
                else lft[i][j] = X;
                L = lft[i + 1][j]; R = rgt[i + 1][j]; X = a[i];
                if(L == X) rgt[i][j] = 0;
                else if(R > X && L > X) rgt[i][j] = X;
                else if(R <= X && L > X) rgt[i][j] = X - 1;
                else if(R > X && L < X) rgt[i][j] = X + 1;
                else rgt[i][j] = X;
            }
        }
        puts(a[1] == lft[2][n] ? "0" : "1");
    }
    return 0;
}