#include<iostream>
#include<algorithm>
using namespace std;
#define N 100
int mat[N][N],mat1[N][N];
struct point{
	int x,y;
}d[4]={{0,-1},{1,0},{0,1},{-1,0}},a[N*N];//


void dp(int n,int r,int c)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<4;j++)
		{
			int t1=a[i].x+d[j].x,t2=a[i].y+d[j].y;
			if(t1<r&&t1>-1&&t2<c&&t2>-1&&mat[t1][t2]<mat[a[i].x][a[i].y]&&mat1[a[i].x][a[i].y]<mat1[t1][t2])
			{
				mat1[a[i].x][a[i].y]=mat1[t1][t2];
            }

		}
		mat1[a[i].x][a[i].y]++;
	}
}
		
bool tmp(const point & p1,const point & p2)  
{
	return  mat[p1.x][p1.y]<mat[p2.x][p2.y];
}
int main()
{
	memset(mat1,0,sizeof(mat1));
	int r,c;
	cin>>r>>c;
	int i,j,n=r*c;
	for(i=0;i<r;i++)
		for(j=0;j<c;j++)
		{
			cin>>mat[i][j];
			a[i*c+j].x=i;
			a[i*c+j].y=j;
		}
	sort(a,a+n,tmp);
	dp(n,r,c);
	j=0;
	for(i=1;i<n;i++)j=mat1[a[j].x][a[j].y]>mat1[a[i].x][a[i].y]?j:i;
	cout<<mat1[a[j].x][a[j].y]<<endl;
	return 0;
}





	

• Re:先前用暴搜32MS，，，后来改dp却变47MS 郁闷.. (14) drcrow 2010-11-25 20:22:58