题解 [AGC048D] Pocky Game
FZzzz
·
·
题解
题目名里的 pocky game 就是指两个人从两端吃一根 pocky 饼干吃到中间亲上的那种游戏，嗑到了嗑到了。
鬼才出题人怎么这也要拿来出题，是不是在跟女朋友玩这的时候突然想到的。
用序列 a 表示一开始的石子数，b 表示游戏进行到某时的石子数。
结论：只考虑非空的堆，在其他堆的石子数不变的情况下，第一堆石子越多越有利于先手。证明显然。
可以带来的推论是只会进行两种操作：拿一个和拿一堆。证明留给读者。
并且第一个结论启发我们求出第一堆最少需要多少石子才能使先手赢。考虑进行 dp，设：
考虑第 l 和第 r 堆其中之一被取空之前两个玩家的策略：
- 先手：如果此时 b_r<g_{l+1,r}，那么直接把第 l 堆取空可以给后手留下一个必败的局面，所以直接取空；否则取空会给后手留下必胜的局面，那么只取一个。
- 后手：如果此时 b_l<f_{l,r-1}，那么直接把第 r 堆取空可以给先手留下一个必败的局面，所以直接取空；否则取空会给先手留下必胜的局面，那么只取一个。
也就是说，过程一定形如：两人轮流每次取一个，直到某次先手行动时 b_r<g_{l+1,r} 或某次后手行动时 b_l<f_{l,r-1}。先手必胜就是要第一种情况先发生，那么要求开始时 b_r<g_{l+1,r} 或 b_l-f_{l,r-1}>b_r-g_{l+1,r}。故：
f_{l,r}=\begin{cases}1&a_r<g_{l+1,r}\\f_{l,r-1}-g_{l+1,r}+a_r+1&a_r\ge g_{l+1,r}\end{cases}
至此我们完整解决了问题，时间复杂度 $O(n^2)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline ll read(){
ll x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') f=1;
c=getchar();
}
while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}
return f?-x:x;
}
const int maxn=100+5;
int n,a[maxn];
ll f[maxn][maxn],g[maxn][maxn];
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int T=read();
while(T--){
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) f[i][i]=g[i][i]=1;
for(int i=n;i>0;i--) for(int j=i+1;j<=n;j++){
f[i][j]=a[j]<g[i+1][j]?1:f[i][j-1]-g[i+1][j]+a[j]+1;
g[i][j]=a[i]<f[i][j-1]?1:g[i+1][j]-f[i][j-1]+a[i]+1;
}
printf(a[1]>=f[1][n]?"First\n":"Second\n");
}
#ifdef LOCAL
fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
#endif
return 0;
}
```