南山网站设计电话,新闻稿代写,课程开发公司,网站备案在哪查problem
AtCoder
solution
注意#xff1a;本题不是平等博弈#xff0c;因为先手只能取最左边#xff0c;后手只能取最右边。
设 f[l][r][k]:f[l][r][k]:f[l][r][k]: 只剩下区间 [l,r][l,r][l,r] 等待操作#xff0c;第 lll 堆石子数量为 kkk 的时候#xff0c;先手是…problem
AtCoder
solution
注意本题不是平等博弈因为先手只能取最左边后手只能取最右边。
设 f[l][r][k]:f[l][r][k]:f[l][r][k]: 只剩下区间 [l,r][l,r][l,r] 等待操作第 lll 堆石子数量为 kkk 的时候先手是否必胜。
同理g[l][r][k]:g[l][r][k]:g[l][r][k]: 只剩下区间 [l,r][l,r][l,r] 等待操作第 rrr 堆石子数量为 kkk 的时候后手是否必胜。
显然如果 f/g[l][r][k]f/g[l][r][k]f/g[l][r][k] 可以必胜那么 f/g[l][r][k1]f/g[l][r][k1]f/g[l][r][k1] 也能必胜无非是有次操作多取一颗石子。
所以不妨设 f[l][r]:f[l][r]:f[l][r]: 只剩下区间 [l,r][l,r][l,r] 操作先手必胜时第 lll 堆石子数量至少为多少。
同理可得g[l][r]:g[l][r]:g[l][r]: 只剩下区间 [l,r][l,r][l,r] 操作后手必胜时第 rrr 堆石子数量至少为多少。
接下来考虑转移转移都只与 f[l][r−1],g[l1][r]f[l][r-1],g[l1][r]f[l][r−1],g[l1][r] 有关。 f[l][r]f[l][r]f[l][r] 若 g[l1][r]a[r]g[l1][r]a[r]g[l1][r]a[r]。 那么先手可以直接取完 lll 堆使得后手面临 [l1,r][l1,r][l1,r] 的必败局面。 因此只需要保证 lll 堆有石子就行了。 f[l][r]1f[l][r]1f[l][r]1 若 g[l1][r]≤a[r]g[l1][r]\le a[r]g[l1][r]≤a[r] 那么先手肯定不能一次取完使后手处于必胜局面。只能一个一个地取。 我们知道至少取 f[l][r]−f[l][r−1]1f[l][r]-f[l][r-1]1f[l][r]−f[l][r−1]1 个石子后先手就会因接下来后手的操作陷入必败状态。 因为此时 lll 堆石子个数 f[l][r−1]f[l][r-1]f[l][r−1]后手直接取完 rrr 堆留给先手的就是 [l,r−1][l,r-1][l,r−1] 的必败状态了。 而后手则至少取 a[r]−g[l1][r]1a[r]-g[l1][r]1a[r]−g[l1][r]1 个就会陷入必败状态。原因同上。也就是说后手也不敢一次取完只能一个一个地取。 此时想要先手获胜必须先手更晚进入必败状态。 即 f[l][r]−f[l][r−1]1a[r]−g[l1][r]1f[l][r]-f[l][r-1]1a[r]-g[l1][r]1f[l][r]−f[l][r−1]1a[r]−g[l1][r]1 ⇒f[l][r]a[r]−g[l1][r]f[l][r−1]\Rightarrow f[l][r]a[r]-g[l1][r]f[l][r-1]⇒f[l][r]a[r]−g[l1][r]f[l][r−1]。 f[l][r]a[r]−g[l1][r]f[l][r−1]1f[l][r]a[r]-g[l1][r]f[l][r-1]1f[l][r]a[r]−g[l1][r]f[l][r−1]1 g[l][r]g[l][r]g[l][r] 若 f[l][r−1]a[l]f[l][r-1]a[l]f[l][r−1]a[l]。 那么后手可以直接取完 rrr 堆使得先手面临 [l,r−1][l,r-1][l,r−1] 的必败局面。 因此只需要保证 rrr 堆有石子就行了。 g[l][r]1g[l][r]1g[l][r]1 若 f[l][r−1]≤a[l]f[l][r-1]\le a[l]f[l][r−1]≤a[l] 那么后手肯定不能一次取完使先手处于必胜局面。只能一个一个地取。 后手至少取 g[l][r]−g[l1][r]1g[l][r]-g[l1][r]1g[l][r]−g[l1][r]1 个就会陷入必败状态。 先手至少取 a[l]−f[l][r−1]1a[l]-f[l][r-1]1a[l]−f[l][r−1]1 个就会陷入必败状态。 此时必须后手更晚进入必败状态。 即 g[l][r]−g[l1][r]1a[l]−f[l][r−1]1g[l][r]-g[l1][r]1a[l]-f[l][r-1]1g[l][r]−g[l1][r]1a[l]−f[l][r−1]1 ⇒g[l][r]a[l]g[l1][r]−f[l][r−1]\Rightarrow g[l][r]a[l]g[l1][r]-f[l][r-1]⇒g[l][r]a[l]g[l1][r]−f[l][r−1]。 g[l][r]a[l]g[l1][r]−f[l][r−1]1g[l][r]a[l]g[l1][r]-f[l][r-1]1g[l][r]a[l]g[l1][r]−f[l][r−1]1
区间 dpdpdp 转移即可时间复杂度 O(n2)O(n^2)O(n2)。
code
#include bits/stdc.h
using namespace std;
#define maxn 105
#define int long long
int T, n;
int a[maxn];
int f[maxn][maxn], g[maxn][maxn];signed main() {scanf( %lld, T );while( T -- ) {memset( f, 0, sizeof( f ) );memset( g, 0, sizeof( g ) );scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld, a[i] );for( int len 2;len n;len )for( int l 1;l n;l ) {int r l len - 1;if( r n ) break;if( g[l 1][r] a[r] ) f[l][r] 1;else f[l][r] a[r] f[l][r - 1] - g[l 1][r] 1;if( f[l][r - 1] a[l] ) g[l][r] 1;else g[l][r] a[l] g[l 1][r] - f[l][r - 1] 1;}if( f[1][n] a[1] ) printf( First\n );else printf( Second\n );}return 0;
}
