#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define maxn 110
#define min(a,b) (a)>(b)?(b):(a)
#define Mem(a,b) memset((a),(b),sizeof((a)))
using namespace std;
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int R, C, G[maxn][maxn], num[maxn][maxn],vis[maxn][maxn];
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };
int dp(int x, int y){
	if (vis[x][y]) return num[x][y];
	for (int i = 0; i < 4; i += 1)
	{
		int nx = x + dx[i], ny = y + dy[i];
		if (nx > 0 && nx <= R && ny > 0 && ny <= C && G[nx][ny]<G[x][y]){
			num[x][y] = max(num[x][y], dp(nx, ny) + 1);
		}
	}
	vis[x][y] = 1;
	return num[x][y];
}
int main(){
	cin >> R >> C;
	for (int i = 1; i <= R; i += 1){
		for (int j = 1; j <= C; j += 1)
			cin >> G[i][j];
	}
	Mem(vis, 0);
	Mem(num, 0); int ans = 0;
	for (int i = 1; i <= R; i += 1){
		for (int j = 1; j <= C; j += 1)
			ans = max(dp(i, j), ans);
	}
	cout << ans + 1<< endl;
	return 0;
}

• Re:记忆化DP (1320) happy_Michael 2019-07-21 16:23:02