题解 P1508 【Likecloud-吃、吃、吃】
officeyutong
2017-10-01 11:51:50
#蒟蒻的题解
思路:记忆化搜索
```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);
}
```