题解：P16531 [THUPC 2026 决赛] 棋盘对弈游戏

· · 题解

题意简述

两枚棋子从位置 1,2 出发。双方轮流让自己的棋子向右跳 1 至 4 格，落点不能是已经占据的格子。每到达一个新格子，当前玩家获得该格子的分值。

双方都采用最优策略，求游戏结束时先手得分减去后手得分。

解题思路

任意时刻，把位置靠右的棋子称为前棋，另一枚称为后棋。棋子只会向右移动，所以后棋左侧的格子以后不可能再到达。前棋右侧的格子则一定尚未占据。状态只需额外记录两枚棋子之间的占据情况。

先处理两枚棋子相距较远的情况。设前棋位于 x，后棋位于 y，当前轮到前棋行动。当 x-y\ge6 时，两侧游戏已经分离。

前棋可以每次移动一格，依次取得 x 右侧的所有格子。这样形成的连续占据段也会阻止后棋进入右侧。后棋则只会在原区间 (y,x) 内移动。

反过来，从后棋之后最靠左的可达格子开始考虑。由于每次移动不超过 4，任何仍能越过的已占据段都可以直接跳过。若出现连续四个已占据格子，后棋本来就不可能到达其右侧。该右侧部分已经由前棋的连续移动封住。因此，后棋最终取得区间内所有尚未占据且仍属于左侧的格子。

所有分值都为正。任何一方跳过自己能够依次取得的格子，都只会永久放弃正收益，也不能侵入另一侧。因此，这个局面的后续分差已经确定。若区间占据掩码为 s，其值为：

\sum_{i=x+1}^n a_i-\sum_{\substack{y<i<x\\i\text{ 未占据}}}a_i

其余需要决策的状态满足 x-y\le5，区间长度至多为 4。用不超过 4 位的二进制数 s 记录区间内哪些格子已被占据。

定义 F(o,x,y,s) 为当前行动者未来能够得到的最大分差。其中 x>y。o=0 表示当前玩家控制前棋，o=1 表示控制后棋。

若当前棋子跳到 z，本次立即得到 a_z。下一状态改由对手决策，所以当前选择的价值为：

a_z-F(o',x',y',s')

枚举所有合法落点并取最大值即可。下面分别说明掩码变化。

前棋从 x 跳到 z 时，旧位置 x 留在新区间内。它相对 y 的位数是 x-y-1，所以将这一位置加入 s，新状态为 (1,z,y,s')。

后棋跳到仍在 x 左侧的 z 时，新的区间左端点变为 z。原掩码中不超过 z 的部分已经失效。因此，把 s 右移 z-y 位，新状态为 (0,x,z,s')。

若后棋跳过前棋，到达 z>x，它会成为新的前棋。旧区间内的格子全部位于两枚新棋子的左侧，不必继续记录。下一位行动者控制旧前棋，也就是新后棋，所以新状态为 (1,z,x,0)。

若当前玩家无合法落点，本回合直接跳过，状态参数不变，只需交换行动者并将结果取负。当 x=n 且后棋也没有合法落点时，双方都不能行动，状态值为 0。

距离 d=x-y 与掩码可以紧凑编号。长度为 d-1 的掩码共有 2^{d-1} 个。把所有更小距离的编号段依次放在前面，编号为：

(2^{d-1}-1)+s

所有需要记忆化的状态都满足 d<6，所以编号小于 31。每个位置只需保存两种行动方和常数个局部状态。

代码按前棋位置、后棋位置从右到左预先调用状态。前棋移动会增大前棋位置。后棋留在左侧时会增大后棋位置，越过前棋时则会增大新的前棋位置。除立即终止的分离状态外，所有依赖都已经计算。因此，递归不会形成长度为 O(n) 的调用链。

每个局部状态枚举至多 4 个落点。时间复杂度为 O(n)，空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
const int S=32;
const ll inf=4000000000000000000LL;
int n,tim;
ll a[N],sum[N],f[2][N][S];
int tag[2][N][S];
bool can(int x,int y,int s)
{
    for(int i=y+1;i<=n&&i<=y+4;i++)
    {
        if(i==x||(s>>(i-y-1)&1))continue;
        return 1;
    }
    return 0;
}
ll dfs(int o,int x,int y,int s)
{
    int d=x-y;
    if(x==n&&!can(x,y,s))return 0;
    if(!o&&d>=6)
    {
        ll ans=sum[n]-sum[x];
        for(int i=y+1;i<x;i++)
        {
            if(!(s>>(i-y-1)&1))ans-=a[i];
        }
        return ans;
    }
    int id=-1;
    if(d<6)
    {
        id=(1<<(d-1))-1+s;
        if(tag[o][y][id]==tim)return f[o][y][id];
    }
    ll ans=-inf;
    bool flag=0;
    if(!o)
    {
        for(int i=x+1;i<=n&&i<=x+4;i++)
        {
            flag=1;
            int ns=s|(1<<(d-1));
            ans=max(ans,a[i]-dfs(1,i,y,ns));
        }
        if(!flag)ans=-dfs(1,x,y,s);
    }
    else
    {
        for(int i=y+1;i<=n&&i<=y+4;i++)
        {
            if(i==x||(s>>(i-y-1)&1))continue;
            flag=1;
            if(i<x)
            {
                int ns=s>>(i-y);
                ans=max(ans,a[i]-dfs(0,x,i,ns));
            }
            else ans=max(ans,a[i]-dfs(1,i,x,0));
        }
        if(!flag)ans=-dfs(0,x,y,s);
    }
    if(d<6)
    {
        tag[o][y][id]=tim;
        f[o][y][id]=ans;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        a[1]=a[2]=0;
        sum[0]=sum[1]=sum[2]=0;
        for(int i=3;i<=n;i++)
        {
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
        tim++;
        for(int i=n;i>=2;i--)
        {
            for(int j=i-1;j>=1&&j>=i-5;j--)
            {
                for(int k=0;k<(1<<(i-j-1));k++)
                {
                    dfs(0,i,j,k);
                    dfs(1,i,j,k);
                }
            }
        }
        cout<<dfs(1,2,1,0)<<'\n';
    }
    return 0;
}