UVA - 10285 Longest Run on a Snowboard （线性DP）

        思路：d[x][y]表示以(x, y)作为起点能得到的最长递减序列，转移方程d[x][y] = max(d[px][py] + 1)，此处(px, py)是它的相邻位置并且该位置的值小于(x, y)处的值。可以选择把所有坐标根据值的大小升序排序，因为值较大的坐标取决于值更小的相邻坐标。

AC代码：

#include<cstdio>#include<algorithm>#include<cstring>#include<utility>#include<string>#include<iostream>#include<map>#include<set>#include<vector>#include<queue>#include<stack>using namespace std;#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int> const int maxn = 100 + 5;int a[100][100];vector<PI>pos[105];char s[100];int n, m, d[maxn][maxn];const int dx[] = {0,0,-1,1};const int dy[] = {1,-1,0,0}; int solve() {	int ans = 0;	for(int i = 0; i <= 100; ++i) {		int len = pos[i].size();		for(int j = 0; j < len; ++j) {			int x = pos[i][j].first, y = pos[i][j].second;			int v = a[x][y];			d[x][y] = 1;			for(int k = 0; k < 4; ++k) {				int px = x + dx[k], py = y + dy[k];				if(px < 0 || py < 0 || px >= n || py >= m) continue;				if(a[px][py] >= a[x][y]) continue;				d[x][y] = max(d[x][y], d[px][py] + 1);			}			ans = max(ans, d[x][y]);		} 	}	return ans;}int main() {	int T;	scanf("%d", &T);	while(T--) {		for(int i = 0; i <= 100; ++i) pos[i].clear();		scanf("%s%d%d", s, &n, &m);		for(int i = 0; i < n; ++i)			for(int j = 0; j < m; ++j) {				scanf("%d", &a[i][j]);				pos[ a[i][j] ].push_back(make_pair(i, j));			}		PRintf("%s: %d/n", s, solve());	}	return 0;}
如有不当之处欢迎指出！