#include <iostream>
using namespace std;
int cmp(const void * a, const void * b) {
	return ((Height*) a)->height - ((Height*) b)->height;
}
struct Height {
	int height;
	int x;
	int y;
};
int Skiing2(int **h, int max, int row, int line) {

	Height H[row * line];
	for (int i = 0, k = 0; i < row; i++) {
		for (int j = 0; j < line; j++) {
			H[k].height = h[i][j];
			H[k].x = i;
			H[k++].y = j;
		}
	}
	qsort(H, row * line, sizeof(Height), cmp);
	int m[row][line];
	int maxm;
	int flag;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < line; j++) {
			m[i][j] = 1;
		}
	}
	for (int i = 1; i < row * line; i++) {
		int k=H[i].height;
		int hx = H[i].x;
		int hy = H[i].y;
		maxm = 0;
		flag = 0;
		if ((hx - 1) >= 0 && h[hx - 1][hy] < k) {
			if (maxm <= m[hx - 1][hy]) {
				maxm = m[hx - 1][hy];
				flag = 1;
			}
		}
		if ((hx + 1) < row && h[hx + 1][hy] < k) {
			if (maxm <= m[hx + 1][hy]) {
				maxm = m[hx + 1][hy];
				flag = 1;
			}
		}
		if ((hy - 1) >= 0 && h[hx][hy - 1] < k) {
			if (maxm <= m[hx][hy - 1]) {
				maxm = m[hx][hy - 1];
				flag = 1;
			}
		}
		if ((hy + 1) < line && h[hx][hy+ 1] < k) {
			if (maxm <= m[hx][hy + 1]) {
				maxm = m[hx][hy + 1];
				flag = 1;
			}
		}
		if(flag==1){
			m[hx][hy]=maxm+1;
		}


	}
	maxm=0;
	for (int i = 0; i < row; i++) {
			for (int j = 0; j < line; j++) {
				if(maxm<m[i][j])maxm=m[i][j];
			}
		}
	return maxm;

}
void SkiingMain() {
	int row;//行
	int line;//列
	cin >> row;
	cin >> line;
	int **h;
	h = new int*[row];
	for (int i = 0; i < row; i++) {
		h[i] = new int[line];
	}
	int max = 0;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < line; j++) {
			cin >> h[i][j];
			if (max < h[i][j])
				max = h[i][j];
		}
	}
	cout<<Skiing2(h, max, row, line);
	//Skiing(h,max,row,line);
}
int main(){
	SkiingMain();
}

• Re:没有人放标准的dp 我放个标准的dp解法把 (31) vvilp 2009-03-27 00:30:29