专栏文章

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

ttanghaocheng
P14169题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minws3h4
此快照首次捕获于
2025/12/02 09:37
3 个月前
此快照最后确认于
2025/12/02 09:37
3 个月前
查看原文

简要题面

给定 N,M,X,TN,M,X,T 和数组 AA，求 11 个长度为 MM 的数组 PP，使得：
  • 对于 i(1≤i≤M)i(1 \le i \le M)，1≤Pi≤N1 \le P_i \le N。
  • ∣P2−P1∣+∣P3−P2∣+⋯+∣PM−PM−1∣≤T|P_2-P_1| + |P_3-P_2| + \cdots + |P_M-P_{M-1}| \le T。
求以下式子的最大值。 (A1,max⁡(P1−X,1)+A1,max⁡(P1−X)+1+⋯+A1,min⁡(P1+X,N))+(A2,max⁡(P2−X,1)+A2,max⁡(P2−X,1)+1+⋯+A2,min⁡(P2+X,N))+(AM,max⁡(PM−X,1)+AM,max⁡(PM−X,1)+1+⋯+AM,min⁡(PM+X,N))(A_{1,\max(P_1-X,1)} + A_{1,\max(P_1-X)+1} + \cdots + A_{1,\min(P_1+X,N)}) + (A_{2,\max(P_2-X,1)} + A_{2,\max(P_2-X,1)+1} + \cdots + A_{2,\min(P_2+X,N)}) + (A_{M,\max(P_M-X,1)} + A_{M,\max(P_M-X,1)+1} + \cdots + A_{M,\min(P_M+X,N)})

测试点 1∼51 \sim 5

直接 NMN^M 暴力枚举数组 PP，判断是否满足上面 22 个式子，求解答案即可。
时间复杂度 O(NM)\mathcal{O}(N^M)，空间复杂度 O(N×M)\mathcal{O}(N \times M)。
代码如下：
CPP
#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∼106 \sim 10

考虑 dp，dpi,j,edp_{i,j,e} 表示是现在考虑到了第 ii 行，Pi←jP_i \gets j，共计花费 ee 的体力。
转移则是再枚举 11 维 kk，表示 Pi−1P_{i-1} 的值。
则转移方程可表示为： dpi,j,e←max⁡(dpi−1,k,e−∣k−j∣+(Ai,max⁡(j−X,1)+Ai,max⁡(j−X,1)+1+⋯+Ai,min⁡(j+X,N)))dp_{i,j,e} \gets \max(dp_{i-1,k,e-|k-j|} + (A_{i,\max(j-X,1)} + A_{i,\max(j-X,1)+1} + \cdots + A_{i,\min(j+X,N)}))
不难发现，(Ai,max⁡(j−X,1)+Ai,max⁡(j−X,1)+1+⋯+Ai,min⁡(j+X,N))(A_{i,\max(j-X,1)} + A_{i,\max(j-X,1)+1} + \cdots + A_{i,\min(j+X,N)}) 的部分可以预处理出来，单独用一个数组存储。
时间复杂度 O(N2×M×T)\mathcal{O}(N^2 \times M \times T)，空间复杂度 O(N×M×T)\mathcal{O}(N \times M \times T)。
代码如下：
CPP
#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∼1511 \sim 15

T=0T = 0，也就代表李老师会一直站在一个位置，换言之，P1=P2=⋯=PMP_1 = P_2 = \cdots = P_M。
枚举 PP 的值，暴力计算答案即可。
时间复杂度 O(N×M×X)\mathcal{O}(N \times M \times X)，空间复杂度 O(N×M)\mathcal{O}(N \times M)。
代码如下：
CPP
#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],ans;
signed main()
{
	off;
	int C;
	cin>>C;
	while(C--)
	{
		ans=0;
		cin>>n>>m>>X>>T;
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++)
			{
				cin>>a[i][j];
			}
		}
		for(int i=1;i<=n;i++)
		{
			int cnt=0;
			for(int k=max((int)(1),i-X);k<=min(n,i+X);k++)
			{
				for(int j=1;j<=m;j++)
				{
					cnt+=a[j][k];
				}
			} 
			ans=max(ans,cnt);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

测试点 26∼3026 \sim 30

特殊性质 A，以及 X=0X=0。
对于每一个时刻，都可以选择花费一定的代价去获得 11 点贡献。
设第 ii 行 Ai,Qi=1A_{i,Q_i}=1。
可以定义 dp 状态，dpi,jdp_{i,j} 表示对于前 ii 分钟，第 ii 分钟获得这点贡献的且总共花费为 jj 的最大答案。
转移时再枚举上 11 次获得贡献是什么时候，设为时刻 kk，则转移为： dpi,j=max⁡(dpk,∣Qj−Qk∣)+1dp_{i,j}=\max(dp_{k,|Q_j-Q_k|})+1
时间复杂度 O(M2×T)\mathcal{O}(M^2 \times T)，空间复杂度 O(M×T)\mathcal{O}(M \times T)。
代码如下：
CPP
#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∼106 \sim 10 的 dp 思路，观察到 max⁡(dpi−1,k,e−∣k−j∣)\max(dp_{i-1,k,e-|k-j|}) 的部分的复杂度可以进行优化。
先将转移拆解，对于每个点，它可以从上一次在它左侧和它右侧转移过来。
考虑从左侧转移的情况。
若在本行我们选择了第 ii 个点，我们在上一行选择了第 i−1i-1 个点，则我们要花费 11 的体力。
我们是不是可以换一下思路，如果上次我们选了第 i−1i-1 个点，我们也可以考虑在这次前走到第 ii 个点，花费 11 点体力。
那这样就好办了，我们定义 prei,j,kpre_{i,j,k} 为第 ii 行，决策完毕后，从左侧走到第 jj 列，共计花费 kk 的体力的最大答案。
则转移为： prei,j,k←max⁡(prei,j−1,k−1,dpi,j,k)pre_{i,j,k} \gets \max(pre_{i,j-1,k-1},dp_{i,j,k})
prei,j−1,k−1pre_{i,j-1,k-1} 指从 j−1j-1 的位置走过来，花费 11 体力；dpi,j,kdp_{i,j,k} 指这一行选择第 jj 个点。
从右侧过来的同理可维护一个 sufsuf 数组。
这样我们会得到 11 份 MLE\color{orange} \text{MLE} 的代码。
观察到，3003300^3 个 int\text{int} 在 64MB64 \text{MB} 的空间下是不够的，而答案又会超过 unsigned short\text{unsigned short} 的范围，所以我们需要用滚动数组。
时间复杂度 O(M×N×T)\mathcal{O}(M \times N \times T)，空间复杂度 O(N×T)\mathcal{O}(N \times T)。
代码如下：
CPP
#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],f[2][N][N],pre[N][N],suf[N][N],cnt[N][N],tmp[N],ans;
signed main()
{
	off;
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>X>>T;
		memset(a,0,sizeof(a));
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++)
			{
				cin>>a[i][j];
			}
		}
		memset(f,0,sizeof(f));
		memset(pre,0,sizeof(pre));
		memset(suf,0,sizeof(suf));
		memset(cnt,0,sizeof(cnt));
		memset(tmp,0,sizeof(tmp));
		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=1;i<=n;i++)
		{
			for(int j=0;i+j<=n;j++)
			{
				pre[i+j][j]=f[1][i][0];
			}
		}
		for(int i=n;i>0;i--)
		{
			for(int j=0;i-j>0;j++)
			{
				suf[i-j][j]=f[1][i][0];
			}
		}
		for(int i=2,op=0;i<=m;i++,op=1-op)
		{
			for(int j=1;j<=n;j++)
			{
				for(int k=0;k<=T;k++)
				{
					f[op][j][k]=max(pre[j][k],suf[j][k])+cnt[i][j];
				}
			}
			memset(pre,0,sizeof(pre));
			memset(suf,0,sizeof(suf));
			memset(tmp,0,sizeof(tmp));
			for(int j=1;j<=n;j++)
			{
				for(int k=T;k>0;k--)
				{
					tmp[k]=tmp[k-1];
				}
				tmp[0]=0;
				for(int k=0;k<=T;k++)
				{
					tmp[k]=max(tmp[k],f[op][j][k]);
				}
				for(int k=0;k<=T;k++)
				{
					pre[j][k]=tmp[k];
				}
			}
			memset(tmp,0,sizeof(tmp));
			for(int j=n;j>0;j--)
			{
				for(int k=T;k>0;k--)
				{
					tmp[k]=tmp[k-1];
				}
				tmp[0]=0;
				for(int k=0;k<=T;k++)
				{
					tmp[k]=max(tmp[k],f[op][j][k]);
				}
				for(int k=0;k<=T;k++)
				{
					suf[j][k]=tmp[k];
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=T;j++)
			{
	//			cout<<i<<' '<<f[m%2][i][j]<<'\n'; 
				ans=max(ans,f[m%2][i][j]);
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...