我先把输入的数据排序，
然后从高度最小的格子开始计算出路径长度值，直至计算完高度最大的格子。
这应该也算是dp了吧？

请大侠看看有什么地方错了？感觉逻辑挺简单的，可是老WA。真烦人
－－－－
/* skiing.c
 * acm pku edu cn - 1088
 * dynamic programming
 */

#include <stdio.h>

typedef struct pair {
	int index;
	int value;
} pair;

int my_max(int m1, int m2, int m3, int m4)
{
	int mx = m1;
	if(m2 > mx)
		mx = m2;
	if(m3 > mx)
		mx = m3;
	if(m4 > mx)
		mx = m4;
	return mx;
}

void swap(pair *m1, pair *m2)
{
	pair tmp = {
		.index = m1->index,
		.value = m1->value,
	};
	m1->index = m2->index;
	m1->value = m2->value;

	m2->index = tmp.index;
	m2->value = tmp.value;
}

int split(pair *vp, int length, int start, int end)
{
	int i = start;
	int x = vp[start].value;
	int j;
	for(j= i+1; j<end+1; j++) {
		if(vp[j].value < x) {
			i++;
			if(i != j)
				swap(&vp[i], &vp[j]);
		}
	}
	swap(&vp[start], &vp[i]);
	return i;
}

void quicksort(pair *vp, int length, int start, int end)
{
	int w;
	if(start < end) {
		w = split(vp, length, start, end);
		quicksort(vp, length, start, w-1);
		quicksort(vp, length, w+1, end);
	}
}

void my_sort(pair *vp, int length)
{
	//sort
	int start = 0, end = length-1;
	quicksort(vp, length, start, end);
}

int get_max(int *value, int length, int start, int end)
{
	int middle, m1, m2;
	if(end-start == 1)
		return value[end]>value[start]?value[end]:value[start];
	else if(end == start)
		return value[end];
	middle = start + (end-start)/2;
	m1 = get_max(value, length, start, middle);
	m2 = get_max(value, length, middle+1, end);

	return m1>m2?m1:m2;
}

int skiing(int *array, int m, int n, int *value)
{
	int result = 0;
	int i,v, k;
	int c, r;

	int up, down, left, right;
	pair *vp = malloc(sizeof(pair)*m*n);

	if(vp == NULL)
		exit(-1);

	for(i=0; i<m*n; i++) {
		vp[i].index = i;
		vp[i].value = array[i];
	}
	//sort vp by "vp[i].value"
	my_sort(vp, m*n);
#ifdef DEBUG
	for(i=0; i<m*n; i++) {
		printf("%d, %d\n", vp[i].index, vp[i].value);
	}
#endif
	//dynamic programming
	for(i=0; i<m*n; i++) {
		c = vp[i].index/n;
		r = vp[i].index%n;
		
		if(c-1 >= 0 && vp[i].value > array[vp[i].index-n])
			up = value[vp[i].index-n];
		else up = 0;
		
		if(c+1 < m && vp[i].value > array[vp[i].index+n])
			down = value[vp[i].index+n];
		else down = 0;

		if(r-1 >= 0 && vp[i].value > array[vp[i].index-1])
			left = value[vp[i].index-1];
		else left = 0;

		if(r+1 >= 0 && vp[i].value > array[vp[i].index+1])
			right = value[vp[i].index+1];
		else right = 0;

		v = value[vp[i].index];
		k = 1+my_max(up, down, right, left);
		if(k > v)
			value[vp[i].index] = k;
	}
	//get the max from value[m][n]
	result = get_max(value, m*n, 0, m*n-1);

	free(vp);
	return result;
}

int main()
{
	//get the input
	int r, c;
	int *array, *value;
	int result;
	int i, j;
	scanf("%d %d", &r,&c);
	fflush(stdin);
	array = malloc(r*c*sizeof(int));
	value = malloc(r*c*sizeof(int));;

	for(i = 0; i<r; i++) {
		for(j=0; j<c; j++) {
			scanf("%d", &array[i*c+j]);
			value[i*c+j] = 1;
		}
		fflush(stdin);
	}
	result = skiing(array, r, c, value);

	printf("%d\n", result);

	free(array);
	free(value);
	return 0;
}