题目链接
题目解法
好难的题,想不出来一点!!!
首先给出一个第一个结论:最优策略下,每个人每次只会取一个石子或者取完一堆石子
题解区都没有严谨证明,\(at\) 的 \(editorial\) 也没证,所以我只能感性理解:
下面以先手为例。如果最左边的石子数 \(>\) 其余所有堆的石子数,那么先手只要一个一个取完这堆,就是必胜的
先手需要找到这样的一堆石子满足上面的条件,但在找到之前,它需要用前面的石子堆和后手消耗,最优的策略是:一次要么取一个消耗,要么全部取完赶到目标的石子堆,不可能出现取 \(>1\) 个但不取完的情况
第二个结论是:以先手为例,先手当前的石子堆的大小越大越好
有了第一个结论,这一个结论就不难说明了
如果当前的石子堆是目标堆,那么显然越大越好
如果不是,那么可以消耗的石子多,如果不用消耗,可以直接取完,所以也是越大越好
下面的我还是想不到 /ll
考虑一个 \(dp\)
令 \(f_{l,r}\) 为当前是先手操作,先手占据第 \(l\) 堆,后手占据第 \(r\) 堆,且 \([l+1,r]\) 堆都没动过,第 \(l\) 堆至少需要的石子数,同理定义 \(g_{l,r}\) 表示当前是后手操作,先手占据第 \(l\) 堆,后手占据第 \(r\) 堆,且 \([l,r-1]\) 堆都没动过,第 \(r\) 堆至少需要的石子数
考虑转移,这里以 \(f_{l,r}\) 为例
- \(g_{l+1,r}>a_r\),那么就是说,先手取完第 \(l\) 堆的话,先手必胜,所以 \(f_{l,r}=1\)
- \(g_{l+1,r}\le a_r\),那么先手肯定是需要一个一个取来消耗,后手从 \(a_r\) 开始取,最优肯定是一个一个取到 \(g_{l+1,r}\),然后取完,所以步数为 \(a_r-g_{l+1,r}+1\),所以 \(f_{l,r}=f_{l,r-1}+a_r-g_{l+1,r}+1\)
边界是 \(f_{i,i}=1\)
如果 \(f_{1,n}\le a_1\),先手必胜,否则后手必胜
时间复杂度 \(O(Tn^2)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=110;
int a[N];
LL f[N][N],g[N][N];
void work(){
int n=read();
F(i,1,n) a[i]=read();
F(i,1,n) f[i][i]=g[i][i]=1;
F(len,2,n) F(l,1,n-len+1){
int r=l+len-1;
//f[l][r]
if(g[l+1][r]>a[r]) f[l][r]=1;
else f[l][r]=a[r]-g[l+1][r]+1+f[l][r-1];
//g[l][r]
if(f[l][r-1]>a[l]) g[l][r]=1;
else g[l][r]=a[l]-f[l][r-1]+1+g[l+1][r];
}
if(f[1][n]>a[1]) puts("Second");
else puts("First");
}
int main(){
int T=read();
while(T--) work();
return 0;
}
标签:ch,int,题解,石子,取完,long,AGC048D,Game,define
From: https://www.cnblogs.com/Farmer-djx/p/17974665