B4140 题解

思路

首先按照题意，初始化

a

矩阵。然后以每个点为起点做 dfs，记录其总和。设要从点

(x_0,y_0)

到点

(x_1,y_1)

，只需要满足

a_{x_1,y_1}>a_{x_0,y_0}

即可移动，移动时加上

a_{x_1,y_1}

。最终统计答案最大值即可。

AC CODE

CPP

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=105;
int a[N][N],ans,dx[]={0,-1,1,0,0},dy[]={0,0,0,-1,1};
void dfs(int x,int y,int sum){
	ans=max(ans,sum);
	for(int i=1;i<=4;++i){
		int xx=x+dx[i],yy=y+dy[i];
		if(a[xx][yy]>a[x][y])
			dfs(xx,yy,sum+a[xx][yy]);
	}
	return;
}
int main(){
	int n=read(),m=read(),s=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			s=s*345%19997;
			a[i][j]=s%10+1;
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			dfs(i,j,a[i][j]);
	printf("%d\n",ans);
	return 0;
}

文章操作

思路

相关推荐

评论

B4140 题解