[数据结构与算法]【博弈】取石子游戏（P2599）

正题

P2599

题目大意

给n堆石子，第 i 堆有 $a_i$ 个石子，每次可以从最左边或者最右边的一堆里面取若干个，两个人轮流取，问先手是否存在必胜策略

解题思路

设 $l_{i,j}$ 为在 $[i,j]$ 右边添加一堆大小 $l_{i,j}$ 的石子，会使得先手必败，$r_{i,j}$同理

首先证明 $l_{i,j}$ 只存在一个

如果存在两个 $l_{i,j}$，那么先手显然可以从大的直接操作为小的，那么先手必胜，不满足先手必败，所以最多有一个 $l_{i,j}$

接下来证明一定存在 $l_{i,j}$

如果不存在 $l_{i,j}$，那么左边无论加多少个数都是必胜状态
如果先手选左边那么必定到必胜状态，不满足先手必胜，所以先手肯定选右边
选了若干数后，一定满足无论左边加的是多少都必败，那么后手在左边选一个数则又回到了必败状态，不满足先手必胜

综上，必定存在 $l_{i,j}$

同理必定存在 $r_{i,j}$ 且只存在一个

接下来考虑如何转移

对于 $l_{i,j}$ 的求解，考虑从 $[i,j?1]$ 转移，那么必定和 $l_{i,j?1},r_{i,j?1}$ 有关，令 $L=l_{i,j?1},R=r_{i,j?1}$

1. $R=a_j$，那么先手就是必败的，所以 $l_{i,j}=0$
2. 对于其他情况，其实就是把必败的决策点除外，令左右必胜决策点数相同即可
   如果先手左边拿到 L，那么右边直接取空则先手必败（右边同理）
   如果先手左边拿完，那么对于后手就是必胜得状态
   否则先手左边拿多少必胜决策，右边拿同样多即可

最后判断 $a_1$ 是否等于 $l_{2,n}$ 即可

时间复杂度 $O(n^{2}T)$

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 1010
using namespace std;
int T,n,a[N],l[N][N],r[N][N];
int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			l[i][i]=r[i][i]=a[i];
		}
		for(int len=2;len<n;++len)
			for(int i=1;i<=n-len+1;++i){
				int j=i+len-1,L,R;
				L=l[i][j-1];R=r[i][j-1];
				if(a[j]==R)l[i][j]=0;
				else if(L<=a[j]&&a[j]<R)l[i][j]=a[j]+1;
				else if(a[j]<L&&a[j]<R)l[i][j]=a[j];
				else if(L<a[j])l[i][j]=a[j];
				else l[i][j]=a[j]-1;
				L=l[i+1][j];R=r[i+1][j];
				if(a[i]==L)r[i][j]=0;
				else if(R<=a[i]&&a[i]<L)r[i][j]=a[i]+1;
				else if(a[i]<R&&a[i]<L)r[i][j]=a[i];
				else if(R<a[i])r[i][j]=a[i];
				else r[i][j]=a[i]-1;
			}
		if(l[2][n]!=a[1])puts("1");
		else puts("0");
	}
	return 0;
}

超强干货来袭

云风专访：近40年码龄，通宵达旦的技术人生