蒟蒻の问
查看原帖
蒟蒻の问
389540
imfkwk楼主2021/1/30 00:23

用记忆化搜索MLE的,大概我是第一人罢

#include <bits/stdc++.h>
using namespace std;

int h[101][101];
int r, c;
int f[101][101];
int ans;

int fx[] = {0, 1, 0, -1};
int fy[] = {1, 0, -1, 0};

int dfs(int x, int y) {
	if (f[x][y]) return f[x][y];
	
	int re = 1;
	
	for (int i = 0; i < 4; i++) {
		int tx = x + fx[i];
		int ty = y + fy[i];
		if (tx > r || tx < 1 || ty > c || ty < 1) continue;
		if (h[tx][ty] > h[x][y]) continue;
		
		re = max(re, dfs(tx, ty) + 1);
	}
	
	f[x][y] = re;
	ans = max(ans, re);
	
	return re;
}

int main(void) {
	scanf("%d%d", &r, &c);
	for (int i = 1; i <= r; i++)
	for (int j = 1; j <= c; j++)
	scanf("%d", &h[i][j]);
	
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			if (!f[i][j]) {
				dfs(i, j);
			}
		}
	}
	
	printf("%d", ans);
	
	return 0;
}

还望能找出问题()

2021/1/30 00:23
加载中...