hbhz_zcy @ 2021-08-02 20:52:57
没看题解，思路如下：
易知从大到小和从小到大是一个东西，因此
维护原数组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;
}by long_int @ 2021-09-10 13:21:47
@38432386zcy 帮你改了一下，A了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#pragma warning (disable : 4996)
const int maxn = 1100, tx[4] = { 0,0,-1,1 }, ty[4] = { -1,1,0,0 };
LL a[maxn][maxn], l[maxn][maxn];
LL ii;
struct node { LL v, x, y; }s[maxn * maxn];
bool cmp(node x, node y) { return x.v < y.v; }
int main() {
LL m, n;
scanf("%lld%lld", &m, &n);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
scanf("%lld", &a[i][j]); l[i][j]++;
s[++ii].v = a[i][j], s[ii].x = i, s[ii].y = j;
}
}
sort(s + 1, s + ii + 1, cmp);
for (int i = ii; i >=1; 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);
}
}
LL ans = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
ans = max(ans, l[i][j]);
cout << ans;
return 0;
}by hbhz_zcy @ 2021-09-13 09:33:03
@Cuber_xh 感谢，问题已解决，ans出了点问题。
#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);
int ans=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
ans=max(ans,l[i][j]);
printf("%d\n",ans);
return 0;
}