#include"iostream.h"

int high[102][102];
int path[102][102];
int x[10700];

inline int cmp(int i)
{return high[x[i]%101][x[i]/101];}




 void quicksort(int n,int m)
{int s;
int i=n+1,j=m;
if(n>=m)return;

while(i<j)
{
while(cmp(n)>=cmp(i)&&i<j)i++;
while(cmp(n)<=cmp(j)&&j>i)j--;

if(cmp(i)>cmp(j)){s=x[i];x[i]=x[j];x[j]=s;}
}

if(cmp(i)>cmp(n))i--;

s=x[i];x[i]=x[n];x[n]=s;
quicksort(n,i-1);
quicksort(i+1,m);
}





int main()
{int n,m,i,j,h,a,b,t,best;
cin>>n>>m;
for(i=0;i<=n+1;i++)path[i][0]=path[i][m+1]=0;

for(i=0;i<=m+1;i++)path[0][i]=path[n+1][i]=0;


h=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{cin>>high[i][j];path[i][j]=0;x[h++]=i+j*101;}

quicksort(0,m*n-1);
j=m*n-1;
best=1;


for(h=0;h<m*n;h++)
{a=x[j]%101;
 b=x[j]/101;
 j--;
t=0;
if(high[a-1][b]>high[a][b]&&path[a-1][b]>t)t=path[a-1][b];
if(high[a+1][b]>high[a][b]&&path[a+1][b]>t)t=path[a+1][b];
if(high[a][b-1]>high[a][b]&&path[a][b-1]>t)t=path[a][b-1];
if(high[a][b+1]>high[a][b]&&path[a][b+1]>t)t=path[a][b+1];
path[a][b]=t+1;
if(best<path[a][b])best=path[a][b];
}
cout<<best<<endl;

return 1;
}

• 动态规划就可以了 (1280) Alpha 2004-05-25 21:39:15