猿辅导笔试第二题

dp[i][j][k]:从i,j出发用k次机会的最长距离．

//dp[k][i][j]:拥有k把锁，人位于i，j时走过的最大步数 #include<iostream> #include<vector> using namespace std; vector<int> dx{ 0,1,-1,0 }; vector<int> dy{ 1,0,0,-1 }; int max(int a, int b) {     return a>b ? a : b; } int main() {     int N, M, K;     cin >> N >> M >> K;     vector<vector<vector<int>>> dp(K + 1, vector<vector<int>>(N, vector<int>(M, 1)));     vector<vector<int>> Tmap(N, vector<int>(M));     for (int i = 0; i<N; i++)         for (int j = 0; j<M; j++)             cin >> Tmap[i][j];     bool key = true;     int result = 0;     while (key) {         key = false;         for (int k = 0; k <= K; k++) {             vector<vector<int>> dp0(dp[k]);             for (int i = 0; i<N; i++)                 for (int j = 0; j<M; j++) {                     int temp = dp[k][i][j];                     for (int dxy = 0; dxy<4; dxy++) {                         int x = i + dx[dxy], y = j + dy[dxy];                         if (x<0 || x >= N || y<0 || y >= M)continue;                         if (Tmap[x][y] >= Tmap[i][j]) {                             if (k<K)                                 dp[k][i][j] = max(dp[k][i][j], dp[k + 1][x][y] + 1);                         }                         else                             dp[k][i][j] = max(dp[k][i][j], dp0[x][y] + 1);                     }                     result = max(result, dp[k][i][j]);                     if (temp<dp[k][i][j])key = true;//dp有更新代表还有位置能走                 }         }     }     cout << result << endl;     return 0; }

参考楼上，Java题解 package Interview2020.YuanFuDao._2; import java.util.Scanner; /** * 深搜+记忆集 * WA * dp[i][j][k]表示从map[i][j]出发，有k把锁的最大移动距离 */ public class Main { private static int[][][] dp; private static int[][] map; private static int N,M,K; private static int[] dx = {-1,1,0,0}; private static int[] dy = {0,0,-1,1}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); K = sc.nextInt(); map = new int[N][M]; for(int i=0 ; i < N; i++){ for(int j=0; j < M; j++){ map[i][j] = sc.nextInt(); } } //初始化DP数组 dp = new int[N][M][K+1]; for(int i=0; i < N; i++){ for(int j=0; j < M; j++){ for(int k=0; k <= K; k++){ dp[i][j][k] = -1; } } } //遍历所有的情况 int res = 0; for(int i=0; i < N; i++){ for(int j=0; j < M; j++){ for(int k=0; k <= K; k++){ res = Math.max(res,dfs(i,j,k)+1); } } } System.out.println(res); } private static int dfs(int i,int j, int k){ //递归终止条件 if(dp[i][j][k] != -1){ return dp[i][j][k]; } int ans = 0; for(int d=0; d < 4; d++){ int nx = i + dx[d]; int ny = j + dy[d]; if(nx >= 0 && nx < N && ny >= 0 && ny < M){ if(map[i][j] <= map[nx][ny]){ if(k >= 1){ ans = Math.max(ans,dfs(nx,ny,k-1)+1); } else{ ans = Math.max(ans,0); } } else{ ans = Math.max(ans,dfs(nx,ny,k)+1); } } } dp[i][j][k] = ans; return ans; } }

DP来做可能可以

只能过20

60% 带备忘录可能可以过吧 没时间想了。。。 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int k = in.nextInt(); int[][] maze = new int[n][m]; int[] x = new int[]{0,0,1,-1}; int[] y = new int[]{-1,1,0,0}; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) maze[i][j] = in.nextInt();   } int max = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++){ int num = maxStep(maze, x, y, k, m, n, i, j); if(num > max) max = num;   } } System.out.println(max);   } static int maxStep(int[][] maze, int[] x, int[] y, int k, int m, int n, int a, int b) { int max = 0; for(int g = 0; g < x.length; g++) { int l = a + x[g]; int r = b + y[g]; if(l >= 0 && l < n && r >=0 && r < m && ( maze[l][r] > maze[a][b] || k > 0 )) { int step; if(maze[l][r] > maze[a][b]) step = maxStep(maze, x, y, k, m, n, l, r); else   step = maxStep(maze, x, y, k-1, m, n, l, r); if(step > max) max = step;   } } return max + 1;   } }

if(mat[x][y] < mat[nx][ny]) dp[x][y][kk] = max(dp[x][y][kk], dfs(nx, ny, kk) + 1); if(mat[x][y] >= mat[nx][ny] && kk > 0) dp[x][y][kk] = max(dp[x][y][kk], dfs(nx, ny, kk - 1) + 1);

写了半天递归，20，

用个队列无脑bfs，20，不想做了

0 20 40 已跪

深度搜索

60, 0, 0 已跪

迷宫，穷举，不过我只有40%，等大佬

类似剑指offer上有个回溯法的题吗？忘了

应该是递归，但是我不会做。哭

写不下去交卷了 第一题我都想死  逻辑没问题 代码写不出来。。。