zxfinal.cpp

acm.pku.edu.cn上面滑雪一题

#include<stdio.h>
int v[100][100],x[100][100],a[10000],b[10000]; 
int f(int l,int h)
{
   int t,p;
   p=l;l++;
   while(l<h)
   {
   if (a[p]<=a[h]) h--;
   else if (a[p]>a[l]) l++;
   else {t=a[l];a[l]=a[h];a[h]=t;
         t=b[l];b[l]=b[h];b[h]=t;
   }
   }
   if (a[h]<a[p])
   {t=a[h];a[h]=a[p];a[p]=t;t=b[h];b[h]=b[p];b[p]=t;return h;}
   else
   {t=a[h-1];a[h-1]=a[p];a[p]=t;t=b[h-1];b[h-1]=b[p];b[p]=t;return h-1;}
}
int g(int l,int h)
{
  int k;
  if (l<h)
    {k=f(l,h);
     g(l,k-1);
     g(k+1,h);    
    }
}
main()
{
    int i,j,l,h,m,n,max;
    scanf("%d %d",&m,&n);
    l=0;
    for (i=0;i<m;i++)
       for (j=0;j<n;j++)
       { scanf("%d",&v[i][j]);
         b[l]=l;
         a[l++]=v[i][j];
         x[i][j]=0;
         }
    l=m*n;
    g(0,l-1);
    max=0;
    for (h=0;h<l;h++)
    {
        j=b[h]%n;
        i=(b[h]-j)/n;
        x[i][j]=1;
        if ((i-1>=0)&&(x[i-1][j]+1>x[i][j])&&(v[i-1][j]<v[i][j])) x[i][j]=x[i-1][j]+1;
        if ((i+1<m)&&(x[i+1][j]+1>x[i][j])&&(v[i+1][j]<v[i][j])) x[i][j]=x[i+1][j]+1;
        if ((j-1>=0)&&(x[i][j-1]+1>x[i][j])&&(v[i][j-1]<v[i][j])) x[i][j]=x[i][j-1]+1;
        if ((j+1<n)&&(x[i][j+1]+1>x[i][j])&&(v[i][j+1]<v[i][j])) x[i][j]=x[i][j+1]+1; 
        if (max<x[i][j]) max=x[i][j];  
        }
    printf("%d\n",max);
    }