什么破题啊
简直就是浪费我时间！
我每天还被我xf定目标了不知道嘛！
朴素的搜索只能得90分
#include <cstdio> #include <iostream> using namespace std; const int N = 110; bool vis[N][N]; int n, m, mp[N][N], ans; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; int read() { int s = 0, w = 1; char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} return s * w; } void dfs(int xx, int yy, int sum) { ans = max(ans, sum); for(int i = 0; i < 4; i++) { int x = dx[i] + xx, y = dy[i] + yy; if(x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && mp[x][y] < mp[xx][yy]) dfs(x, y, sum + 1); } } int main() { n = read(), m = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) mp[i][j] = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) dfs(i, j, 0); printf("%d\n", ans + 1); return 0; }
需要加入记忆化搜索
真想骂街我的记忆化怎么怎么就不对
可能是我太毛躁了
于是我就点开了题解
Code：
#include <cstdio> #include <iostream> using namespace std; const int N = 110; int n, m, mp[N][N], ans, maxn[N][N]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; int read() { int s = 0, w = 1; char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} return s * w; } int dfs(int xx, int yy) { if(maxn[xx][yy] != 1) return maxn[xx][yy]; int anss = 0; for(int i = 0; i < 4; i++) { int x = dx[i] + xx, y = dy[i] + yy; if(x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] < mp[xx][yy]) anss = max(anss, dfs(x, y) + 1); maxn[xx][yy] = max(maxn[xx][yy], anss); } return maxn[xx][yy]; } int main() { n = read(), m = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) mp[i][j] = read(), maxn[i][j] = 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { int anss = dfs(i, j); ans = max(ans, anss); } printf("%d ", ans); return 0; }
TTT，TnmT！不是脏话
谢谢收看，祝身体健康！（反正我是被气死了）
京公网安备 11010502036488号