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

int cmp(const void*a,const void*b){
	return ((Point*)a)->h-((Point*)b)->h;
}
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;
	for (i=1;i<n;i++){
		for (j=i-1;j>=0;j--){//point j below point i
			if (CanGo(i,j,0)==true){//left
				snowlen[i][0]=max(j)+1;break;
			}
			if (CanGo(i,j,1)==true){//right
				snowlen[i][1]=max(j)+1;break;
			}
			if (CanGo(i,j,2)==true){//up
				snowlen[i][1]=max(j)+1;break;
			}
			if (CanGo(i,j,3)==true){//down
				snowlen[i][1]=max(j)+1;break;
			}
		}
	}
	cout<<max(n-1)+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
				&& Snowarea[i].h>Snowarea[j].h) return true;
	case 1: if (Snowarea[j].r==Snowarea[i].r 
				&& Snowarea[j].c==Snowarea[i].c+1
				&& Snowarea[i].h>Snowarea[j].h) return true;
	case 2: if (Snowarea[j].r==Snowarea[i].r-1 
				&& Snowarea[j].c==Snowarea[i].c
				&& Snowarea[i].h>Snowarea[j].h) return true;
	case 3: if (Snowarea[j].r==Snowarea[i].r+1 
				&& Snowarea[j].c==Snowarea[i].c
				&& Snowarea[i].h>Snowarea[j].h) return true;
	}
	return false;
}

int max(int j){
	int temp=0;
	int k;
	for (k=0;k<4;k++){
		if (snowlen[j][k]>snowlen[j][temp])	temp=k;
	}
	return snowlen[j][temp];
}

• 我现在改过了，可是却成tle了？请指教 (1847) testjoan 2006-04-10 17:59:08
  • 是不是不能用dp？还是我的方法不对？ (2003) testjoan 2006-04-10 21:16:08
    • 就是dp (0) frkstyc 2006-04-10 21:36:44
• Re:我是模仿1661写的，可以吗？为什么wa？ (1920) firelandy 2006-06-02 23:36:34