【纪中模拟2019.08.02】【JZOJ1308】取数游戏

题目链接

 

题意：

　　N个正整数围成一圈，规则如下：

•两个玩家轮流取数；•先手玩家取任意一个数x；•从第二步开始当前玩家只能取x（上一玩家取的数）相邻的数；•直到取完所有的数，游戏结束；•取得较多奇数的玩家获胜。

　　保证双方都采取最优策略的同时，计算先手有多少种取法获胜。

　　$1\le N\le 10^2,\quad 1\le x\le 10^3$

 

分析：

　　因为笔者不会SG函数，所以如果有绕弯子的描述请谅解。

　　分析博弈过程，有$2^n$种形势，按博弈写程序会$TLE$。

　　考虑DP，貌似取数的过程有后效性，然而这是因为不熟悉环的性质（套路）导致。事实上，当你取走环上一个数，并规定只能操作原数两端的其他数的时候，可以看做把环由某点断开、展平，并规定只能在这个区间的两端取数。所以第二步及以后的所有取数操作都不再具有后效性了，可以区间DP。

　　于是我们知道，只能枚举$n$种展开方式，如果能获胜，令答案$+1$。

　　定义$f_{i,j}$表示对于两倍延展环之后的区间$[i,j]$（长度$<n$），先手取数比后手多取得奇数的个数，那么有$$f_{i,j}=max\{\,a_i-f_{i+1,j}\,,\,a_j-f_{i,j-1}\,\}$$

　　先后手的转换：取相反数。

　　注意区间左端点的取值范围：它和区间长度有关。要做全$2n$内的所有区间情况。

 

 代码（100分）：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define IL inline using namespace std; const int N=100; int n,a[N*2+3]; int f[N*2+3][N*2+3]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) a[i]&=1; for(int i=1;i<=n;i++) a[i+n]=a[i]; for(int i=1;i<=n*2;i++) f[i][i]=a[i]; for(int t=2;t<=n;t++) for(int i=1;i+t-1<=n*2;i++){ int j=i+t-1; f[i][j]=max(a[i]-f[i+1][j],a[j]-f[i][j-1]); } int ans=0; for(int i=1;i<=n;i++) if(a[i]-f[i+1][i+n-1]>0) ans++; printf("%d",ans); return 0; }

 

 

小结：

　　遇到问题多想两步，别一刀砍死，可能有转机。

 

转载于:https://www.cnblogs.com/Hansue/p/11295432.html

相关资源：JAVA上百实例源码以及开源项目