AGC048D-Pocky Game

重要结论：对于先手和后手，每次要么取 $1$ 个石子，要么取完这堆石子。

非严谨证明：若当前自己所在的堆中石子个数满足大于剩下所有还存在的石子个数，那么显然只要每次取 $1$ 个石子，等到对手取完剩下所有堆之后，自己取完这堆就能胜利。

若是小于等于，那么我们肯定不考虑占据该堆，而是考虑找到第一个满足大于剩下所有还存在的石子数的堆，显然这一定是最优策略。

那么通过这个结论我们考虑区间 $dp$。

设 $f_{l,r}$ 表示 $(l,r]$ 是原 $a$ 序列，当前先手在 $l$ 堆至少取多少石子能赢。

设 $g_{l,r}$ 表示 $[l,r)$ 是原 $a$ 序列，当前后手在 $r$ 堆至少取多少石子能赢。

显然，先手能赢肯定是满足 $f_{1,n} \le a_1$，反之后手赢。

那么我们考虑状态转移，其实就是考虑每一方在什么时候会赢，以及最优策略下该如何行动。

• 先手：考虑当前到了 $l$ 堆，那么意味着先把这一堆拎出来，然后比较。若 $g_{l+1,r}>a_r$，那么先手只要取完 $l$ 堆就可以获胜，反之就得考虑后手下一步的决策情况；若 $g_{l+1,r}\le a_r$ 那么先手此时的操作肯定是尽量拖住后手，也就是说先手当前这一步如果可以赢，那么最少的石子数，就是 $a_r-g_{l+1,r}+1+f_{l,r-1}$，因为我们肯定是先将的局面弄成不能必胜，然后自己考虑从自己得子局面继承过来。显然状态转移就已经满足了博弈论中的先后手都足够聪明，即最佳决策。

• 后手：同理，意味着当前后手可以操作的最有堆该如何取石子，若 $f_{l,r-1}>a_l$，那么后手只要取完那么就必胜了，剩下的思考过程同先手。

那么我们总结一下：

$$\begin{cases} f_{l,l}=1,l=l\\ f_{l,r}=1,g_{l+1,r}>a_r\\ f_{l,r}=a_r-g_{l+1,r}+1+f_{l,r-1},g_{l+1,r}\le a_r\\ \end{cases}$$

$$\begin{cases} g_{l,l}=1,l=l\\ g_{l,r}=1,f_{l,r-1}>a_l\\ g_{l,r}=a_l-f_{l,r-1}+1+g_{l+1,r},f_{l,r-1}\le a_l\\ \end{cases}$$

时间复杂度 $O(n^2)$。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include<iostream>
using namespace std;
const int N=108;
int T,n;
int a[N];
long long f[N][N],g[N][N];//left:f;right:g;
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            f[i][i]=g[i][i]=1;
        }
        for(int l=n;l>=1;l--){
            for(int r=l+1;r<=n;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(a[r]<g[l+1][r]){
                    f[l][r]=1;
                }
                else{
                    f[l][r]=((a[r]-g[l+1][r]+1)+f[l][r-1]);
                }
            }
        }
        if(f[1][n]<=a[1]){
            puts("First");
        }
        else{
            puts("Second");
        }
    }
    return 0;
}

__END__