思路：d[x][y]表示以(x, y)作為起點(diǎn)能得到的最長(zhǎng)遞減序列，轉(zhuǎn)移方程d[x][y] = max(d[px][py] + 1)，此處(px, py)是它的相鄰位置并且該位置的值小于(x, y)處的值。可以選擇把所有坐標(biāo)根據(jù)值的大小升序排序，因?yàn)?#20540;較大的坐標(biāo)取決于值更小的相鄰坐標(biāo)。

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;}
如有不當(dāng)之處歡迎指出！