斧乃木余接 @ 2019-07-23 15:57:49
思路是先把每个点按高度排序,然后从低到高地计算,每一格的滑行长度等于周围较低的点滑行长度+1;一直算到最后一个点输出。样例过了,检查不出哪里有问题T.T数组已经调大了一倍还是一样
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
struct inf
{
int x;
int y;
int h;
}a[20001];
int map[201][201];//记录高度
int pam[201][201];//记录最大滑行长度
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int r,c;//行数R和列数C
bool cmp(inf f,inf s)
{
return f.h<=s.h;
}
int clt(int x,int y)
{
//计算
int maxn=0;
for(int i=1;i<=4;i++)
{
if(map[x+dx[i]][y+dy[i]]<map[x][y]&&pam[x+dx[i]][y+dy[i]]>maxn)
{
maxn=pam[x+dx[i]][y+dy[i]];
}
}
return maxn+1;
}
int main()
{
cin>>r>>c;
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
cin>>map[j][i];
a[(i-1)*c+j].x=j;
a[(i-1)*c+j].y=i;
a[(i-1)*c+j].h=map[j][i];
}
}
// 输入
sort(a+1,a+(r*c+1),cmp);
// 排序
for(int i=1;i<=r*c;i++)
{
pam[a[i].x][a[i].y]=clt(a[i].x,a[i].y);
}
cout<<pam[a[c*r].x][a[c*r].y];
return 0;
}