CF2005E2 Subtangle Game (Hard Version) 题解

· · 题解

不错的 DP 题。

我们先约定一下：以 (i,j) 为左上角的子矩阵，表示以 (i,j)，(i,m)，(n,j)，(n,m) 为四个端点的子矩阵；矩阵均指二维数组 b。

首先我们可以列出 dp_{i,j,k} 表示以 (i,j) 为左上角的子矩阵，且接下来取 a_k，先手是否必胜。我们约定 1 表示必胜，0 表示必败。

然后先考虑朴素转移：

首先可以发现如果以 (i,j) 为左上角的矩阵的子矩阵可以成功（当然当前取的数相同，即 k 相同）的情况下，dp_{i,j,k}=1。

好绕啊！这里有一个形式化一点的表达：

如果存在 x,y 满足 x\ge i 且 y\ge j，dp_{x,y,k}=1，则 dp_{i,j,k}=1。这里可以自行画图理解。

然后考虑特殊情况，b_{i,j}=a_k：

首先容易想到的是从边界出发：

所以如果 i=n 或 j=m 或 k=l，先手必胜。

然后有一个简单转移：考虑取这里，那么后手拿到的是以 (i+1,j+1) 为左上角的子矩阵。那么如果 dp_{i+1,j+1,k+1}=0，先手显然必胜。

这样子就完成 DP 的转移了，复杂度 O(nml)，可以通过 E1。

然后考虑优化。

提示：考虑分析一下样例，或者再看一眼 DP 的朴素转移，有没有什么规律？

我们可以从 DP 的朴素转移里发现两个性质：

首先，如果 dp_{i,j,k}=1，则 dp_{i,j-1,k}=1，这一点显然（再看看朴素转移）。

同理，如果 dp_{i,j,k}=1，则 dp_{i-1,j,k}=1。

从第一个性质推导，我们惊喜的发现好像可以压维，也就是把 j 那一维压掉！

故我们定义 f_{i,k} 表示能使 dp_{i,j,k}=1 的最大的 j。

考虑优化转移（如果 b_{i,j}=a_k，dp_{i+1,j+1,k+1}=0，dp_{i,j,k}=1）：

提示：当 j 变大时，dp_{i+1,j+1,k+1}=0 的可能性是怎样的？

发现如果 b_{i,j}=a_k，那么 j 越大转移成功（即先手获胜）的概率越高。这是一个贪心的想法，证明显然（注意到若 dp_{i,j,k}=1，则 dp_{i,j-1,k}=1，而 dp_{i,j+1,k} 不一定等于 1）。

那么，我们肯定取最大的 j，满足 b_{i,j}=a_k。

于是我们定义 mx_{i,k} 表示使 b_{i,j}=a_k 的最大的 j。我们记 mx_{i,k}=0 表示不存在 b_{i,j}=a_k。

那么这个转移为：若 mx_{i,k}\ne 0 且 mx_{i,k}\ge f_{i+1,k+1}，则 f_{i,k}=mx_{i,k}。

这一点可能有点难，那么讲一下思考过程：

首先我们想让 dp_{i,mx_{i,k},k}=1，所以 dp_{i+1,mx_{i,k}+1,k+1}=0，即 f_{i+1,k+1}<mx_{i,k}+1，即 f_{i+1,k+1}\le mx_{i,k}。

所以若 mx_{i,k}\ne 0 且 mx_{i,k}\ge f_{i+1,k+1}，则 f_{i,k}=mx_{i,k}。

然后考虑 i,j,k 的影响：

首先 j=m 是好写的，显然 f_{i+1,k+1}\le m，所以可以并为上面的转移。

然后 i=n 和 k=l 也简单，f_{i,k}=mx_{i,k}，这里的转移不难。

最后是朴素转移：

首先 y\ge j 的情况不用推了，前面定义的时候就用过了。

然后是 x\ge i 的部分：我们看到第二个性质，如果 dp_{i,j,k}=1，则 dp_{i-1,j,k}=1。所以 f_{i,k}=f_{i+1,k}。

最后对上述所有值取最大值即可。

然后呢？然后就没了。接下来你只需要写一下求 mx 就可以了。

最后考虑输出：如果先手必胜，那么 dp_{i,j,1}=1。然后根据上面的两个性质，不难推出：如果 f_{1,1}\ne 0，那么先手必胜。

时间复杂度：O(nm+nl)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1510;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3f;
int l,n,m;
int a[N];
int b[N][N];
int f[N][N];
int mx[N][N];
int T[N*N];
void solve(){
    cin>>l>>n>>m;
    for(int i=1;i<=l;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>b[i][j];
    for(int i=1;i<=n;i++){//这里开桶记录，如果用map复杂度会多一个log
        for(int j=1;j<=m;j++)T[b[i][j]]=j;
        for(int j=1;j<=l;j++)mx[i][j]=T[a[j]];
        for(int j=1;j<=m;j++)T[b[i][j]]=0;
    }
    for(int k=l;k>=1;k--){
        for(int i=n;i>=1;i--){
            f[i][k]=max(f[i][k],f[i+1][k]);
            if(mx[i][k]>0&&f[i+1][k+1]<=mx[i][k])f[i][k]=max(f[i][k],mx[i][k]);
            if(mx[i][k]>0&&(i==n||k==l))f[i][k]=max(f[i][k],mx[i][k]);
        }
    }
    int fl=0;
    if(f[1][1]>0)fl=1;
    if(!fl)cout<<"N\n";
    else cout<<"T\n";
    for(int i=1;i<=n;i++)
        for(int j=1;j<=l;j++)
            f[i][j]=mx[i][j]=0;
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}
/*
dp[i][j][k]：考虑(i,j)~(n,m)的子矩阵，a到了第k位，先手是否必胜
考虑初始化：dp[i][j][k]=1（其中b[i][j]=a[k]）
考虑转移：
b[i][j]=a[k]:
dp[i][j][k]=(!dp[i+1][j+1][k+1])
i==n or j==m or k==l
b[i][j]!=a[k]:
dp[i][j][k]=dp[x][y][k](i<=x and j<=y)
这是E1的做法
发现转移中，若(i,j)=1，则(i,k)=1 [k<=j]
记：
f[i][k]表示使dp[i][j][k]=1最大的j
mx[i][k]表示使b[i][j]=a[k]最大的j
考虑用这个转移：
f[i][k]=max(mx[i][k],f[i+1][k+1])
i==n or k==l:f[i][k]=mx[i][k]
这是E2的做法
*/