[Algo Beat Contest 002.5 D] 我要当 gamer (gamer) 题解

tanghaocheng · 2025-09-13 22:57:32 · 题解

简要题面

给定 N,M,X,T 和数组 A，求 1 个长度为 M 的数组 P，使得：

• 对于 i(1 \le i \le M)，1 \le P_i \le N。

求以下式子的最大值。

测试点 1 \sim 5

直接 N^M 暴力枚举数组 P，判断是否满足上面 2 个式子，求解答案即可。

时间复杂度 \mathcal{O}(N^M)，空间复杂度 \mathcal{O}(N \times M)。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define ll unsigned long long
#define off ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pi pair<int,int>
#define pii pair<int,pair<int,int> >
using namespace std;
const int N=305;
int n,m,T,X,t,a[N][N],cnt[N][N],ans;
void dfs(int step,int lt,int e,int sum)
{
    if(step>m)
    {
        if(e>=0)
        {
            ans=max(ans,sum);
        } 
        return;
    }
    for(int i=1;i<=n;i++)
    {
        dfs(step+1,i,e-abs(lt-i),sum+cnt[step][i]);
    }
}
signed main()
{
    off;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>X>>T;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>a[i][j];
            }
        }
        memset(cnt,0,sizeof(cnt));
        ans=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k=max((int)(1),j-X);k<=min(n,j+X);k++)
                {
                    cnt[i][j]+=a[i][k];
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            dfs(2,i,T,cnt[1][i]);
        } 
        cout<<ans<<'\n';
    }
    return 0;
}

测试点 6 \sim 10

考虑 dp，dp_{i,j,e} 表示是现在考虑到了第 i 行，P_i \gets j，共计花费 e 的体力。

转移则是再枚举 1 维 k，表示 P_{i-1} 的值。

则转移方程可表示为：

不难发现，(A_{i,\max(j-X,1)} + A_{i,\max(j-X,1)+1} + \cdots + A_{i,\min(j+X,N)}) 的部分可以预处理出来，单独用一个数组存储。

时间复杂度 \mathcal{O}(N^2 \times M \times T)，空间复杂度 \mathcal{O}(N \times M \times T)。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define ll unsigned long long
#define off ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pi pair<int,int>
#define pii pair<int,pair<int,int> >
using namespace std;
const int N=305;
int n,m,T,X,a[N][N],f[N][N][N],cnt[N][N],ans;
signed main()
{
    off;
    int c;
    cin>>c;
    while(c--)
    {
        cin>>n>>m>>X>>T;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>a[i][j];
            }
        }
        memset(f,0,sizeof(f));
        memset(cnt,0,sizeof(cnt));
        ans=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k=max((int)(1),j-X);k<=min(n,j+X);k++)
                {
                    cnt[i][j]+=a[i][k];
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            f[1][i][0]=cnt[1][i];
        }
        for(int i=2;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int e=0;e<=T;e++)
                {
                    for(int k=1;k<=n;k++)
                    {
//                      f[i-1][k][e]->f[i][j][e+abs(k-j)]
                        if(e+abs(k-j)>T)
                        {
                            continue;
                        } 
                        f[i][j][e+abs(k-j)]=max(f[i][j][e+abs(k-j)],f[i-1][k][e]+cnt[i][j]);
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=T;j++)
            {
                ans=max(ans,f[m][i][j]);
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

测试点 11 \sim 15

特殊性质 A，以及 X=0。

对于每一个时刻，都可以选择花费一定的代价去获得 1 点贡献。

设第 i 行 A_{i,Q_i}=1。

可以定义 dp 状态，dp_{i,j} 表示对于前 i 分钟，第 i 分钟获得这点贡献的且总共花费为 j 的最大答案。

转移时再枚举上 1 次获得贡献是什么时候，设为时刻 k，则转移为：

时间复杂度 \mathcal{O}(M^2 \times T)，空间复杂度 \mathcal{O}(M \times T)。

代码如下：

#include<bits/stdc++.h>
#define int long long
#define ll unsigned long long
#define off ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pi pair<int,int>
using namespace std;
const int N=305;
int c,n,m,X,T,q[N],f[N][N],ans;
signed main()
{
    off;
    cin>>c;
    while(c--)
    {
        cin>>n>>m>>X>>T;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int x;
                cin>>x;
                if(x)
                {
                    q[i]=j;
                }
            }
        }
        memset(f,0,sizeof(f));
        for(int i=1;i<=m;i++)
        {
            f[i][0]=1;
            for(int j=1;j<i;j++)
            {
                for(int k=abs(q[i]-q[j]);k<=T;k++)
                {
                    f[i][k]=max(f[i][k],f[j][k-abs(q[i]-q[j])]+1);
                }
            }
        }
        ans=0;
        for(int j=1;j<=m;j++)
        {
            for(int i=0;i<=T;i++)
            {
                ans=max(ans,f[j][i]);
            }
        } 
        cout<<ans<<'\n';
    }
    return 0;
}

正解

延续测试点 6 \sim 10 的 dp 思路，观察到 \max(dp_{i-1,k,e-|k-j|}) 的部分的复杂度可以进行优化。

先将转移拆解，对于每个点，它可以从上一次在它左侧和它右侧转移过来。

考虑从左侧转移的情况。

若在本行我们选择了第 i 个点，我们在上一行选择了第 i-1 个点，则我们要花费 1 的体力。

我们是不是可以换一下思路，如果上次我们选了第 i-1 个点，我们也可以考虑在这次前走到第 i 个点，花费 1 点体力。

那这样就好办了，我们定义 pre_{i,j,k} 为第 i 行，决策完毕后，从左侧走到第 j 列，共计花费 k 的体力的最大答案。

则转移为：