# include <iostream.h>
# include <stdlib.h>
# include <memory.h>
const int T=100*100;
struct Point{
	int r,c;
	int h;
}Snowarea[T];
int snowlen[T][4]={0};//记录第i个点向四个方向0左1右2上3下最长滑雪道长度

int cmp(const void*a,const void*b){
	return ((Point*)a)->h-((Point*)b)->h;
}
int cmpint(const void*a,const void*b){
	return *((int*)b)-*((int*)a);
}

void Findlen(int);
bool CanGo(int,int,int);
int max(int);
void main(){	
	int row,col;
	int i,j,k;	
	cin>>row>>col;
	k=0;
	for (i=1;i<=row;i++){
		for (j=1;j<=col;j++){
			Snowarea[k].r=i;
			Snowarea[k].c=j;
			cin>>Snowarea[k].h;
			k++;
		}
	}
	qsort(Snowarea,row*col,sizeof(Point),cmp);
	Findlen(row*col);
}
void Findlen(int n){
	int i,j;	
	memset(snowlen,0,sizeof(int)*n*4);
	for (i=1;i<n;i++){
		for (j=i-1;j>=0;j--){//point j below point i
			if (Snowarea[i].h==Snowarea[j].h)	continue;
			if (CanGo(i,j,0)==true)		snowlen[i][0]=max(j)+1;
			if (CanGo(i,j,1)==true)		snowlen[i][1]=max(j)+1;
			if (CanGo(i,j,2)==true)		snowlen[i][2]=max(j)+1;
			if (CanGo(i,j,3)==true)		snowlen[i][3]=max(j)+1;
		}
	}
	qsort(snowlen,n*4,sizeof(int),cmpint);
	cout<<snowlen[0][0]+1<<endl;
}

bool CanGo(int i,int j,int direction){
	switch (direction){
	case 0: if (Snowarea[j].r==Snowarea[i].r 
				&& Snowarea[j].c==Snowarea[i].c-1)	return true;
			else	return false;
			break;
	case 1: if (Snowarea[j].r==Snowarea[i].r 
				&& Snowarea[j].c==Snowarea[i].c+1) return true;
			else	return false;
			break;
	case 2: if (Snowarea[j].r==Snowarea[i].r-1 
				&& Snowarea[j].c==Snowarea[i].c) return true;
			else	return false;
			break;
	case 3: if (Snowarea[j].r==Snowarea[i].r+1 
				&& Snowarea[j].c==Snowarea[i].c) return true;
			else	return false;
			break;
	}
}

int max(int j){	
	qsort(snowlen[j],4,sizeof(int),cmpint);
	return snowlen[j][0];
}

• 是不是不能用dp？还是我的方法不对？ (2003) testjoan 2006-04-10 21:16:08
  • 就是dp (0) frkstyc 2006-04-10 21:36:44