💡Yupureki:个人主页
✨个人专栏:《C++》 《算法》
🌸Yupureki🌸的简介:
目录
前言
1. Function
算法原理
实操代码
2. 天下第一
算法原理
实操代码
3. 滑雪
算法原理
实操代码
前言
记忆化搜索也是一种剪枝策略。通过一个”备忘录”，记录第一次搜索到的结果，当下一次搜索到这个状态时，直接在”备忘录”里面找结果。记忆化搜索，有时也叫动态规划。
1. Function
题目链接:
P1464 Function - 洛谷
算法原理
题目叙述的非常清楚，我们仅需按照「题目的要求」把「递归函数」写出来即可。但是，如果不做其余处理的话，结果会「超时」。因为我们递归的「深度」和「广度」都非常大
因此，可以在递归的过程中，把每次算出来的结果存在一张「备忘录」里面。等到下次递归进入「—模一样」的问题之后，就「不用傻乎乎的展开计算」，而是在「备忘录里面直接把结果拿出来」，起到大量剪枝的效果。
实操代码
#include <iostream> #include <string> using namespace std; typedef long long LL; const int N = 25; LL a, b, c; LL f[N][N][N]; LL dfs(LL a, LL b, LL c) { if (a <= 0 || b <= 0 || c <= 0) return 1; if (a > 20 || b > 20 || c > 20) return dfs(20, 20, 20); if (f[a][b][c]) return f[a][b][c]; if (a < b && b < c) return f[a][b][c] = dfs(a, b, c - 1) + dfs(a, b - 1, c - 1) - dfs(a, b - 1, c); else return f[a][b][c] = dfs(a - 1, b, c) + dfs(a - 1, b - 1, c) + dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1); } int main() { while (cin >> a >> b >> c) { if (a == -1 && b == -1 && c == -1) break; printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, dfs(a, b, c)); } return 0; }2. 天下第一
题目链接:
P5635 【CSGRound1】天下第一 - 洛谷
算法原理
用递归模拟整个游戏过程，谁先到0谁赢
而这题的关键在于如何判断平局的情况
关于平局，即双方都无法到达0，可以转化为双方都在循环
例如双方一开始的数字分别为x 和 y ，但兜兜转转又回到了x 和 y。如果有一个能到达0，那么在这个循环中早就跳出了，不会回到起点。因此我们定义一个set<pair<int,int>>，记录每次两个人的数的情况，如果发现在set中早就记录过了，那么说明循环了一次，谁也不会赢
实操代码
#include <iostream> #include <set> using namespace std; int p; int a, b; set<pair<int, int>> s;//记录两个人的数的情况 void dfs() { int tmp = (a + b) % p; if (tmp == 0) { cout << "1" << endl; return; } b = (a + b + b) % p; if (b == 0) { cout << "2" << endl; return; } a = tmp; if (s.find({ a,b }) != s.end())//set中存在该情况，则循环了 { cout << "error" << endl; return; } s.insert({ a,b }); dfs(); return; } int main() { int n; cin >> n>>p; while (n--) { s.clear(); cin >> a >> b; dfs(); } return 0; }3. 滑雪
题目链接:
P1434 [SHOI2002] 滑雪 - 洛谷
算法原理
这题的关键点在于，我们可以选择任意一个格子滑雪，找到最长的路径、
我们当然可以无脑枚举，但时间复杂度过高可能超时，关键在于我们可能会走相同的路径
例如我们我们已经计算出了从某一个格子开始的最长路径，后续我们选择其他格子开始时，中途可能会再次到达该格子，因此如果我们先前记录了该最长路径，就不会再次往下递归了，因此我们需要一个数组来记录每个格子的最长路径
实操代码
#include <iostream> #include <vector> using namespace std; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int n, m; vector<vector<int>> v; vector<vector<int>> mem;//记录从某个格子开始的最长路径 int ret = 0; int dfs(int row,int col) { if (mem[row][col] != 0)//先前已经记录了该格子的最长路径，那么就直接返回该值 return mem[row][col]; int sum = 1; for (int k = 0; k < 4; k++) { int i = row + dx[k]; int j = col + dy[k]; if (i < 0 || i >= n || j < 0 || j >= m || v[i][j] >= v[row][col]) continue; sum = max(dfs(i,j) + 1,sum); } return mem[row][col] = sum; } int main() { cin >> n >> m; v.resize(n); mem.resize(n); for (int i = 0; i < n; i++)//枚举从每个格子开始滑雪 { mem[i].resize(m); for (int j = 0; j < m; j++) { int num; cin >> num; v[i].push_back(num); } } int ret = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { ret = max(dfs(i, j),ret); } } cout << ret; }
