题解 P1508 【Likecloud-吃、吃、吃】

officeyutong

2017-10-01 11:51:50

Solution

#蒟蒻的题解 思路:记忆化搜索 ```cpp #include <cstdio> #include <iostream> #include <vector> #include <array> #include <algorithm> #include <functional> #include <cstdlib> #include <map> using namespace std; using int_t = signed long long int; //矩阵的行数,列数 int_t yMax, xMax; //矩阵 int_t matrix[202][202] = {0}; //要实现记忆化搜索,保存之前的搜索结果 //memory[x][y][已经得到的能量值] map<int_t, int_t> memory[201][201]; //搜索函数 //x:当前x //y:当前y //v:已获得的能量 int_t search(int_t x, int_t y, int_t v) { if (memory[x][y].find(v) != memory[x][y].end()) return memory[x][y][v]; int_t v1 = 0, v2 = 0, v3 = 0; //判断是否可以向左上走 if (x != 1 && y != 1) { v1 = search(x - 1, y - 1, v) + matrix[x - 1][y - 1]; } //判断是否可以向上走 if (y != 1) { v2 = search(x, y - 1, v) + matrix[x][y - 1]; } //判断是否可以向右上走 if (x != xMax && y != 1) { v3 = search(x + 1, y - 1, v) + matrix[x + 1][y - 1]; } //找到最大值 int_t result = max(max(v1, v2), v3); //保存结果 memory[x][y][v] = v + result; return v + result; } int main() { cin >> yMax>>xMax; for (int i = 1; i <= yMax; i++) for (int j = 1; j <= xMax; j++) cin >> matrix[j][i]; cout << search(xMax / 2 + 1, yMax + 1, 0); } ```