玄学60分代码
查看原帖
玄学60分代码
142549
hbhz_zcy楼主2021/8/2 20:52

没看题解,思路如下:

易知从大到小和从小到大是一个东西,因此

  • 维护原数组a,顺序数组s,求解数组l

  • 各个点从小到大排一遍序

  • 从小到大去搜索每一个点,看能否向旁边更大的点扩充并使它的道路长度更大

请问是我的思路错了还是代码的某些细节出现了问题(样例已过得分60pts)

code

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cstring>
using namespace std;
const int maxn=110,tx[4]={0,0,-1,1},ty[4]={-1,1,0,0};
int a[maxn][maxn],l[maxn][maxn];
struct node{int v,x,y;}s[maxn*maxn];
bool cmp(node x,node y){return x.v<y.v;}
int main(){
	memset(l,0,sizeof(l));memset(s,0,sizeof(s));
	int m,n;scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&a[i][j]);l[i][j]++;
			s[i*n+j-n].v=a[i][j],s[i*n+j-n].x=i,s[i*n+j-n].y=j;
		}
	}
	sort(s+1,s+m*n+1,cmp);
	for(int i=1;i<=n*m;i++){
		int v=s[i].v,x=s[i].x,y=s[i].y;
		for(int i=0;i<=3;i++){
			int vx=x+tx[i],vy=y+ty[i];
			if(vx<1||vx>m||vy<1||vy>n)  continue;
			if(a[vx][vy]>v)  l[vx][vy]=max(l[vx][vy],l[x][y]+1);
		}
//	for(int i=1;i<=m;i++){
//		for(int j=1;j<=n;j++){
//			printf("%d ",l[i][j]);
//		}
//		printf("\n");
//	}
//	printf("\n");
	}
//	for(int i=1;i<=m*n;i++)
//		printf("%d:%d %d %d\n",i,s[i].x,s[i].y,s[i].v);
	printf("%d\n",l[s[m*n].x][s[m*n].y]);
	return 0;
}
2021/8/2 20:52
加载中...