社区讨论
第二点一直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 条回复,欢迎继续交流。
正在加载回复...