猿辅导笔试编程题思路（算法岗位）
代码写的不好别喷啊。。。思路就是这么个思路。。
第一题代码别看了，写的不是很优美，就不贴出来了。。
第一题（100）：
根据括号递归，里层括号的输出是外层的输入
第二题（100）：
一个记忆化搜索，dp[i][j][k]代表从i,j出发用k次机会最远的距离
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);
在dfs函数最开始的时候判断一下，如果dp[x][y][k]不等于初始值的时候直接返回就可以了
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#define MAXN 505
#define MAXK 11
using namespace std;
int dp[MAXN][MAXN][MAXK];
int mat[MAXN][MAXN];
int n, m, k, ans;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int dfs(int x, int y, int kk)
{ if(dp[x][y][kk] != -1) return dp[x][y][kk]; dp[x][y][kk] = 1; for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 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); } return dp[x][y][kk];
}
int main()
{ while(scanf("%d%d%d", &n, &m, &k) != EOF) { ans = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { scanf("%d", &mat[i][j]); } } memset(dp, -1, sizeof(dp)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { dp[i][j][k] = dfs(i, j, k); ans = max(ans, dp[i][j][k]); } } printf("%d\n", ans); } return 0;
} 第三题(70):
dp，二维dp，第二维表示当前i状态下是否在手里，转移方程：
dp[i][1] = dp[i - 1][0];
dp[i][0] = ( ( (dp[i - 1][1] * (LL)(k - 1)) % MOD )+ ( (dp[i - 1][0] * (LL)(k - 2)) % MOD) ) % MOD;
感觉过100，可能需要矩阵快速幂优化一下。。但时间不够了
====================================================
想了一下第三题过100%的解法，
设
[ai]
[bi]
ai是当前第i回合在我手里的状态，bi是当前回合在其他人手里的状态
则有ai=bi-1 bi=（k-1）*ai-1+（k-2）*bi-1
即
[ai] = [0 1][ai-1]
[bi] = [k-1 k-2][bi-1]
那么就可以对这个矩阵求一个快速幂模就可以了。。
投递OPPO等公司7个岗位 >