B4140 题解

getchar_unlocked · 2025-03-18 17:45:06 · 题解

题目传送门

思路

首先按照题意，初始化 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

#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;
}