#include <stdio.h>
#include <algorithm>
using std::sort;
const int N = 101;
int lgst[N][N];
struct node{int x, y, h; void set(int xx, int yy, int hh) {x = xx; y=yy; h=hh;}}nd[N*N];
int brd[N][N];
int r, c;

bool operator<(const node& a, const node& b) {
	return a.h < b.h;
}

int main() {
	int i, j;
	scanf("%d%d", &r, &c);
	for(i = 0; i<r; i++) 
		for(j = 0; j<c; j++) {
			scanf("%d", &(brd[i][j]));
			nd[i*c+j].set(i, j, brd[i][j]);
		}
	sort(nd, nd+r*c);
	for(i = 0; i < r; i++)
		for(j = 0; j < c; j++)
			lgst[i][j] = 1;
	int max = 1;
	for(i = 1; i<r*c; i++) {
		int x = nd[i].x;
		int y = nd[i].y;
		int h = nd[i].h;
		if(x > 0 && brd[x-1][y] < h) 
			if(lgst[x-1][y] + 1 > lgst[x][y])
				lgst[x][y] = lgst[x-1][y] + 1;
		if(x < c-1 && brd[x+1][y] < h) 
			if(lgst[x][y] < lgst[x+1][y] + 1)
				lgst[x][y] = lgst[x+1][y] + 1;
		if(y > 0 && brd[x][y-1] < h) 
			if(lgst[x][y-1] + 1 > lgst[x][y])
				lgst[x][y] = lgst[x][y-1] + 1;
		if(y < r-1 && brd[x][y+1] < h)
			if(lgst[x][y] < lgst[x][y+1] +1)
				lgst[x][y] = lgst[x][y+1] + 1;
		if(lgst[x][y] > max) max = lgst[x][y];
	}
	printf("%d\n", max);
	return 0;
}
	

• 你可以把这个过程看作DP :) (1268) rovingcloud 2007-02-13 17:44:01