社区讨论

第二点一直TLE,求大佬指教

P1434[SHOI2002] 滑雪参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6vovts
此快照首次捕获于
2025/11/20 11:35
4 个月前
此快照最后确认于
2025/11/20 11:35
4 个月前
查看原帖
CPP
#include <iostream>
#include <cstdio>
using namespace std;
int N,M;
int X[101][101];
int maxstep=0;
int sx,sy;
int f[101][101];
int walkx[4]={0,0,1,-1},walky[4]={1,-1,0,0};
void dfs(int step,int x,int y);
void read(int &a)
{
    a=0;int d=1;char c;
    while (c=getchar(),c<'0'||c>'9') if (c=='-') d=-1;a=a*10+c-48;
    while (c=getchar(),c>='0'&&c<='9') a=a*10+c-48;
    a*=d;
}
int main()  {
	//freopen("1.txt","r",stdin);
	read(N),read(M);
	for(int i=1;i<=N;i++)  {
		for(int j=1;j<=M;j++)  {
			read(X[i][j]);
			
		}
	}
	for(int i=0;i<=N+1;i++)  {
		for(int j=0;j<=M+1;j++)  {
			f[i][j]=-1;
		}
	}
	for(sx=1;sx<=N;sx++)  {
		for(sy=1;sy<=M;sy++)  {
			dfs(1,sx,sy);
		}
	}
    for(int i=1;i<=N;i++)  {
		for(int j=1;j<=M;j++)  {
			if(f[i][j]>maxstep)  maxstep=f[i][j];
		}
	}
	cout<<maxstep;
	return 0;
}
void dfs(int step,int x,int y)  {
	bool flag=false;
	int nx,ny;
	for(int i=0;i<=3;i++)  {
		nx=x+walkx[i];
		ny=y+walky[i];
		if(nx>=1 && nx<=N && ny>=1 && ny<=M && X[nx][ny]<X[x][y])  {
			flag=true;
			if(f[nx][ny]!=-1 && step+f[nx][ny]>f[sx][sy])  {
				f[sx][sy]=step+f[nx][ny];
			}
			else  dfs(step+1,nx,ny);
		}
	}
	if(flag==false)  {
		f[sx][sy]=max(step,f[sx][sy]);
	} 
	
	return;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...