今天是元宵节，外面的鞭炮声很大。元宵晚会已经成了那些人的KTV了。我还是总结一下白天的题目好了。 是一道在二维数组上的最长下降子序列或者最长上升子序列问题。很自然会用h[i][j]来表示到(i，j)位置的最长上升子序列的长度。考虑状态转移方程，与之有关系的是：

1. h[i - 1][j]
2. h[i][j - 1]
3. h[i + 1][j]
4. h[i][j + 1]

状态转移方程如下：

h[i][j] = max(h[i - 1][j],h[i][j - 1],h[i + 1][j],h[i][j + 1]) + 1,

if  a[i - 1][j] < a[i][j] or a[i][j - 1] < a[i][j] or a[i + 1][j] < a[i][j] or a[i][j + 1] < a[i][j]

上面的状态转移方程没有问题。但是我们更应该关注计算的顺序。如果，按照一行一行的来，会发现，自底向上计算的时候，一些没有计算过。所以，这个顺序是不行的。那只能换个思路，通过思考我们可以知道，在计算最小值的时候，h[i][j]的时候，更小的值没有，就可认为是已经知道的，然后再计算次小的，就是最小的已知，可计算。则可知，需要对高度进行排序。代码如下：

#include #include #include struct Pos {	int x, y, height;};int r, c, m, max_h;int h[110][110], a[110][110];struct Pos map[10100];int d[4][2] = {
   {0, 1}, {0, -1}, {-1, 0}, {1, 0}};int cmp(const void* a,const void* b){    if(((struct Pos*)a)->height > ((struct Pos*)b)->height)        return 1;    if(((struct Pos*)a)->height < ((struct Pos*)b)->height)        return -1;    return 0;}int main() {	scanf("%d%d", &r, &c);	m = 0;	memset(a, sizeof(a), 0);	memset(h, sizeof(h), 0);	for (int i = 1; i <= r; ++i)		for (int j = 1; j <= c; ++j) {			map[m].x = i;			map[m].y = j;			scanf("%d", &map[m].height);			a[i][j] = map[m].height;			h[i][j] = 1;			++m;		}	qsort(map, r * c, sizeof(struct Pos), cmp);	max_h = -1;	for (int i = 0; i < m; ++i) {		for (int j = 0; j < 4; ++j) {			int cx = map[i].x + d[j][0];			int cy = map[i].y + d[j][1];			if (a[cx][cy] < map[i].height && h[map[i].x][map[i].y] <= h[cx][cy])				h[map[i].x][map[i].y] = h[cx][cy] + 1;		}		if (h[map[i].x][map[i].y] > max_h)			max_h = h[map[i].x][map[i].y];	}	printf("%d\n", max_h);	return 0;}