🪴 Edwin Aze's Blog

最近文章

最近笔记

记忆化搜索

8分钟阅读

滑雪

给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

在给定矩阵中，一条可行的滑行轨迹为 24−17−2−1。

在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1，沿途共经过 25 个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

数据范围

1≤R,C≤300,
0≤矩阵中整数≤100000≤矩阵中整数≤10000

输入样例：

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出样例：

25

思路

看到这题肯定能联想到走迷宫的BFS, 但这找的是最长路径。

DFS可以解决最长路径问题, 但需要找到所有可能结果从中选择最优的, 题目300*300 = 9e4 个点, 显然会超时间。

优化方法： 暴力的优化方法第一个就去往DP上想, 这里的话就是每个点可以从哪几个点转移过来, 显然是有四个方向且每个方向有需要条件成立。

但如何确保当前点的转移路径成立呢？ 即转移前的点已经找到到这个点的最长路径。 如果是线性DP的话很简单, 因为从小到大搜的话肯定是之前的路径都成立, 且不会出现之前的某个点依赖于后面的点。

思来想去, 似乎与图论中最短路有点相像, 可以根据当前的最优解来确定当前点的最长路径, 如果出现更好的就直接替换掉。即记住之前做的所有努力, 并在之前的基础上进行搜索。

所以就利用DFS搜索加上最短路的路径记录, 转移思想则取自DP。（什么缝合怪） 缝合起来就得到新的算法：记忆化搜索！

展开！ 状态表示： f[i][j] 以该点结束的路径长度 状态属性： max 状态转移： f[i][j] = max(f[x][y] + 1) 四个方向上, 当然还要满足小于的条件

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e2 + 10;
int f[N][N];
int h[N][N];
int n,m;
int dy[] = {0,0,1,-1}, dx[] = {1,-1,0,0};
 
int dp(int i, int j)
{
	int &v = f[i][j]; 
	if(v != -1) // 如果之前确定过就不再从该点搜
		return v;
	v = 1; // 初始化
	for(int k = 0; k < 4; k++)
	{
		int x = i + dx[k], y = j + dy[k];
		if(x >= 0 && x < n && y >= 0 && y < n && h[i][j] < h[x][y])
		{
			v = max(v, dp(x,y) + 1);
		}
	}
	return v;
}
 
int main()
{
	cin >> n >> m;
	for(int i = 0; i < n;i ++)
		for(int j = 0; j < m; j++)
			cin >> h[i][j];
	int res = 0;
	for(int i = 0; i < n;i ++) // 因为可以停在任意一个点
		for(int j = 0; j < m; j++)
			res = max(res, dp(i,j));
	cout << res << endl;
	return 0;
}

FatMouse and Cheese

有一种游戏是的玩法是这样的：
有一个n*n的格子,每个格子有一个数字。
遵循以下规则:

  1. 玩家每次可以由所在格子向上下左右四个方向进行直线移动，每次移动的距离不得超过m
  2. 玩家一开始在第一行第一列，并且已经获得该格子的分值
  3. 玩家获得每一次移动到的格子的分值
  4. 玩家下一次移动到达的格子的分值要比当前玩家所在的格子的分值要大。
  5. 游戏所有数字加起来也不大，保证所有数字的和不会超过int型整数的范围
  6. 玩家仅能在n*n的格子内移动，超出格子边界属于非法操作
  7. 当玩家不能再次移动时，游戏结束
    现在问你，玩家所能获得的最大得分是多少？

Input

有多组测试数据
每组测试样例第一行是两个整数n,m (1≤n≤100)(1≤m≤100),当n和m都是-1时为程序结束标志，直接退出即可
之后n行，每行n个数字，描述n*n的格子里的数字

Output

对于每组测试数据输出一行，这一行仅有一个整数，代表玩家所能获得的最高得分

Sample Input

3 1
1 2 5
10 11 6
12 12 7
-1 -1

Sample Output

37

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
//------- Coding Area ---------//
const int N = 1e2 + 10, MOD = 100003;
// int f[N][N];
int n, m, res;
int a[N][N], f[N][N];
int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 };
 
int dfs(int xx, int yy)
{
    int& v = f[xx][yy], maxx = 0;
    if (v != -1)
        return v;
    for(int i = 0; i < 4; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            int x = xx + dx[i] * j, y = yy + dy[i] * j;
            if (x <= n && x > 0 && y <= n && y > 0 && a[xx][yy] < a[x][y])
            {
                int temp = dfs(x, y);
                if (temp > maxx)
                    maxx = temp;
            }
        }
    }
    v = maxx + a[xx][yy];
    return v;
}
 
int main()
{
 
    while (cin >> n >> m && (n != -1 && m != -1))
    {
        mem(f, -1);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            cin >> a[i][j];
        cout << dfs(1, 1) << endl;
    }
    return 0;
}