链接:迷宫逃脱【算法赛】 - 蓝桥云课 (lanqiao.cn)
题意
可以考虑记忆化搜索
本人代码只能通过75%样例,写的很乱, 一眼丁真鉴定为依托答辩,代码贴最后了, 先附上ac代码
#include<bits/stdc++.h> using namespace std; using ull = unsigned long long; using ll = long long; using PII = pair<int,int>; #define endl "\n" #define int long long #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0) const int N=1e3+10; const int INF=0x3f3f3f3f; const int mod=1e9+7; int n, m, q; ll g[N][N]; ll mem[N][N][5];//5把钥匙的可以获得的最大值 int dx[] = {1, 0}; int dy[] = {0, 1}; bool check(int x, int y) { if(x <= n && y <= m) return true; return false; } ll dfs(int x, int y, int k) { if(k < 0) return -1e18; if(x == n && y == m) return g[x][y]; if(mem[x][y][k] != -1e18) return mem[x][y][k]; for(int i = 0; i < 2; i ++) { int xx = x + dx[i], yy = y + dy[i]; if(!check(xx, yy)) continue; if(__gcd(g[x][y], g[xx][yy]) == 1) { mem[x][y][k] = max(mem[x][y][k], dfs(xx, yy, k - 1) + g[x][y]); } else mem[x][y][k] = max(mem[x][y][k], dfs(xx, yy, k) + g[x][y]); } return mem[x][y][k]; } signed main() { IOS; cin >> n >> m >> q; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { cin >> g[i][j]; for(int k = 0; k <= q; k ++) { mem[i][j][k] = -1e18; } } } ll res = dfs(1, 1, q); if(res > 0) cout << res; else cout << -1; return 0; }
答辩代码
#include<bits/stdc++.h> using namespace std; using ull = unsigned long long; using ll = long long; using PII = pair<int,int>; #define endl "\n" #define int long long #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0) const int N=1e3+10; const int INF=0x3f3f3f3f; const int mod=1e9+7; int n, m, q; ll g[N][N]; ll dp[N][N][5];//5把钥匙的可以获得的最大值 bool check(int x, int y, int cn) { if(x <= n && y <= m && cn >= 0) return true; return false; } ll dfs(int x, int y, int cn) { //ll p = g[i][j]; if(dp[x][y][cn] != -1) return dp[x][y][cn]; dp[x][y][cn] = 0; ll &t = dp[x][y][cn]; if(check(x + 1, y, cn - 1) && __gcd(g[x + 1][y], g[x][y]) == 1) { t = max(t, dfs(x + 1, y, cn - 1)); } if(check(x, y + 1, cn - 1) && __gcd(g[x][y + 1], g[x][y]) == 1) { t = max(t, dfs(x, y + 1, cn - 1)); } if(check(x + 1, y, cn) && __gcd(g[x + 1][y], g[x][y]) > 1 ) { t = max(t, dfs(x + 1, y, cn)); } if(check(x, y + 1, cn) && __gcd(g[x][y + 1], g[x][y]) > 1) { t = max(t, dfs(x, y + 1, cn)); } //cout << x << ' ' << y << ' ' << t << endl; return dp[x][y][cn] = t + g[x][y]; } signed main() { IOS; cin >> n >> m >> q; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) cin >> g[i][j]; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) for(int k = 0; k <= q; k ++) { dp[i][j][k] = -1; } dfs(1, 1, q); ll res = -1; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) for(int k = 0; k <= q; k ++) res = max(res, dp[i][j][k]); cout << res << endl; return 0; }View Code
标签:cn,int,ll,迷宫,long,using,逃脱,define From: https://www.cnblogs.com/ZouYua/p/17834557.html