题目链接

大意

给你一堆石子，每次只能取最左或最右的石子，问是否有必胜策略。

题解

这道题我们并不能通过Nim/SG的思想做出。
大神们说可以区间dp。
那我们可以设 $L{i,j}$ 表示若在i的左面放 $L{i,j}$ 则先手必输。
类似的我们可以设 $R{i,j}$ 表示若在j的右面放 $R{i,j}$ 则先手必输。

step1

$L{i,j}$,$R{i,j}$ 有且仅有一种答案。

证明唯一性:首先假设存在 $L{i,j}$ 设k可满足先手必输的性质。
若 $k>L{i,j}$,那么假如我把k堆取成 $L{i,j}$ 那么这其实是存在必胜状态，不成立；
若 $k>L{i,j}$,那么假如我把 $L{i,j}$ 堆取成k 那么$L{i,j}$ 存在必胜状态，不成立.
综上 有唯一性。
证明存在性:假如不存在这个$L{i,j}$ 使得为必输情况，那没无论怎么取$L{i,j}$均为必胜。
假如在左面取了k个，那么此时是一个必胜态，所以不能在左面取。
只能在右面取，那么这还是对于任意左面的多少都是必败态，和上述类似，这种是肯定不行的。
故，不存在 “不存在 $L_{i,j}$”的情况。
R可以理解为把L整个数列翻转。

有了存在且唯一性，我们就可以直接找特例的答案；

step2

转移 $L{i,j}$
为了方便记 $l=L{i,j-1}$,$r=R{i,j-1},x=a_j$
首先，我们考虑 $L{i,i}=ai$
因为$a{i-1}=a_{i}$ 后手可以模仿先手，这样后手一定必胜。

假如 $r=x$ 那么：
$L{i,j}=0$
因为，我们定义$R{i,j-1}$ 为在$j-1$ 的右面加上数，所以就是在 j 加上数，而有恰巧为 $a_j$，所以说明本身这个状态为必败。

假如 $x<l,x<r$ 那么：
$L_{i,j}=x$
因为这样我们构造了最左和最右相同的一个状态。
此时我们不管先手怎么取我们都模仿他。
最后肯定是先手取完一堆，然后我们都会剩一堆，此时 $x<l,x<r$ ，所以一定是先手必胜。

假如 $x>l,x>r$ 那么：
$L_{i,j}=x$
证明类似。

假如 $l<x<r$
$L_{i,j}=x+1$
因为我们依旧可以学对面怎么取，假如剩下x，我们依旧可以取成两堆相同的。
这就和上两种一样了。

假如 $r<x<l$
$L_{i,j}=x-1$
同理
这样就可以区间dp了。