acwing滑雪_acwing 滑雪

直接暴力搜索会超时

#include <iostream>

using namespace std;
typedef long long ll;
ll arr[305][305];
int book[305][305];
int m, n;
int maxx = -1;
int nx[] = { -1,0,1,0 };
int ny[] = { 0,1,0,-1 };
void dfs(int x, int y,int len)
{
    if (len > maxx)maxx = len;
    for (int i = 0; i < 4; i++)
    {
        int dx = nx[i] + x;
        int dy = ny[i] + y;
        if (dx<0 || dx>n - 1 || dy<0 || dy>m - 1)
            continue;
        if (arr[dx][dy] < arr[x][y] && book[dx][dy] == 0)
        {
            book[dx][dy] = 1;
            dfs(dx, dy, len + 1);
            book[dx][dy] = 0;
        }
    }
}
int main(void)
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            dfs(i, j,0);
    }
    cout << maxx + 1;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

使用记忆化数组 记录每个点的最大滑动长度
遍历每个点作为起点
然后检测该点四周的点 如果可以滑动到其他的点
那么该点的最大滑动长度 就是其他可以滑到的点的滑动长度+1
dp[i][j] = max(dp[i][j-1], dp[i][j+1],dp[i-1][j],dp[i+1][j])

由于滑雪是必须滑到比当前低的点 所以不会存在一个点多次进入的问题

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll arr[305][305];
int dp[305][305];
int m, n;
int maxx = -1;
int nx[] = { -1,0,1,0 };
int ny[] = { 0,1,0,-1 };
int dfs(int x, int y)
{
    if (dp[x][y])return dp[x][y];
    for (int i = 0; i < 4; i++)
    {
        int dx = nx[i] + x;
        int dy = ny[i] + y;
        if (dx<0 || dx>n - 1 || dy<0 || dy>m - 1)
            continue;
        if (arr[dx][dy] < arr[x][y])
        {
            dp[x][y] = max(dp[x][y],dfs(dx, dy)+1);
        }
    }
    return dp[x][y];
}
int main(void)
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int len = dfs(i, j);
            maxx = max(len, maxx);
        }
    }
    cout << maxx+1;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45