灰色网站建设,网站建设主要步骤,美食网站开发的难点,高端网名这是一个非平等博弈。但是只要求你判断胜负#xff0c;本身也不是一道结论题#xff0c;所以可以用 D P DP DP来解决。
结论#xff1a;第一堆石子剩的越多#xff0c;先手玩家获胜的概率越大。这直接引出了一个非常感性的结论#xff1a;每次取石子时要么取一堆#xf…这是一个非平等博弈。但是只要求你判断胜负本身也不是一道结论题所以可以用 D P DP DP来解决。
结论第一堆石子剩的越多先手玩家获胜的概率越大。这直接引出了一个非常感性的结论每次取石子时要么取一堆要么只取一个。很难理性证明这个博弈策略是正确的但是博弈本身就是很玄学的东西似乎我们找不出来一套普适的理论去判断游戏的胜负。那么只要这个策略本身具有合理性就可以采纳。就这道题而言取一堆石子可以看成是加快游戏进度取一个石子可以看成是让游戏的步数延长。看来这道题当中游戏步数是非常重要的维度我们可以通过比较游戏步数的大小来判定胜负。
然后就是编 D P DP DP状态。设 f l , r f_{l,r} fl,r表示剩 [ l 1 , r ] [l1,r] [l1,r]堆中石子时先手获胜 a l a_l al的最小数目 g l , r g_{l,r} gl,r表示剩 [ l , r − 1 ] [l,r-1] [l,r−1]堆中石子时后手获胜后手先操作 a r a_r ar的最小数目。注意这里我们要求 [ l , r ] [l,r] [l,r]中的石子堆都非空。这个状态给我一种 border \text{border} border的感觉也就是要么左端点被截断或者右端点被截断正好就是对应左右两端中两堆石子被消耗的过程。
接着编具体的转移。其实并不复杂如果 g l 1 , r a r g_{l1,r}a_r gl1,rar那么直接将第 l l l堆取空就行有 f l , r 1 f_{l,r}1 fl,r1否则先手一定是消耗并且 a l 1 a_l1 al1任意时刻如果 a l f l , r − 1 a_lf_{l,r-1} alfl,r−1那么后手就会将第 r r r堆取完从而先手必败那么分类讨论 1.1 1.1 1.1 如果 g l 1 , r 1 g_{l1,r}1 gl1,r1那么一定要是后手取完并且此时 a l a_l al恰好为 f l , r − 1 f_{l,r-1} fl,r−1有 f l , r f l , r − 1 a r f_{l,r}f_{l,r-1}a_r fl,rfl,r−1ar 1.2 1.2 1.2 如果 g l 1 , r ≠ 1 g_{l1,r}\ne 1 gl1,r1那么当 a l f l , r − 1 a_lf_{l,r-1} alfl,r−1时第 r r r堆也恰好为 g l 1 , r − 1 g_{l1,r}-1 gl1,r−1此时再将 a l a_l al取完就变成先手必胜了有 f l , r f l , r − 1 a r − g l 1 , r 1 f_{l,r}f_{l,r-1}a_r-g_{l1,r}1 fl,rfl,r−1ar−gl1,r1。
后手和先手是对称的就不说了。这个 D P DP DP转移还挺容易推错的可能主要是因为没有想到临界时两端的石子数目都不为 0 0 0。
复杂度 O ( n 2 ) O(n^2) O(n2)。
#includebits/stdc.h
#define ll long long
#define fi first
#define se second
#define pb push_back
#define db double
using namespace std;
int T,n;
ll a[105],f[105][105],g[105][105];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinT;while(T--){cinn;for(int i1;in;i)cina[i];memset(f,0x3f,sizeof f),memset(g,0x3f,sizeof g);for(int i1;in;i){f[i][i]1,g[i][i]1;}for(int len2;lenn;len){for(int l1;ln-len1;l){int rllen-1;if(g[l1][r]a[r])f[l][r]1;else f[l][r]f[l][r-1]a[r]-g[l1][r]1;if(f[l][r-1]a[l])g[l][r]1;else g[l][r]g[l1][r]a[l]-f[l][r-1]1;}}if(n1||f[1][n]a[1]){coutFirst\n;}else{coutSecond\n;}}
}
