题意

一个

n \times m

点矩形

a

，给出每个点的权值。CEXE 从第一行出发往下走，每次可以从

a_{i,j}

到达

a_{i+1,j-1},a_{i+1,j},a_{i+1,j+1}

。到达一个点可以取走一个点的权值，求最大权值和。

分析

神秘动态规划。

定义

dp_{i,j}

为到达第

i

行第

j

列的最大权值和，发现由左上、上方、右上可以过来，不难写出转移方程：

dp_{i,j}=\max\{dp_{i-1,j-1},dp_{i-1,j},dp_{i-1,j+1} \}

，其中

2 \le i \le n,1 \le j \le m

。初始化为

dp_{1,i}=a_{1,i}

，其中

1 \le i \le m

。注意多测。

时间复杂度

O(Tnm)

。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define up(_name_,_leftbound_,_rightbound_) for(auto _name_=(_leftbound_);(_name_)<=(_rightbound_);++(_name_))
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m;
int a[105][105];
int dp[105][105];
void solve(int cases){
	n=read(),m=read();
	up(i,1,n){
		up(j,1,m){
			a[i][j]=read();
		}
	}
	memset(dp,0,sizeof(dp));
	up(i,1,m) dp[1][i]=a[1][i];
	up(i,2,n){
		up(j,1,m){
			dp[i][j]=max({dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1]})+a[i][j];
		}
	}
	int maxn=-1;
	up(i,1,m){
		maxn=max(maxn,dp[n][i]);
	}
	cout<<maxn<<endl;
	return;
}
signed main(int argc,char *argv[]){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	T=read();
	up(i,1,T) solve(i);
	return 0;
}
/*
---INFORMATIONS---
TIME:2025/8/5 18:37:51
PROBLEM:SP3923
CODE BY __CrossBow_EXE__ Luogu uid967841
CEXE好闪，拜谢CEXE。
*/

已 AC。

题解：SP3923 BYTESM2 - Philosophers Stone

文章操作

题意

分析

代码

相关推荐

评论

题解：SP3923 BYTESM2 - Philosophers Stone