CSP-J 2020 方格取数 T4

先观察数据范围，我们发现20pts，是可以打暴力拿的。剩下的看样子，就得搞dp。方格中的数值，1e4，1e3 x 1e3 x 1e4需要开一下long long，稳一点，测点有两个挂long long

20pts

// 我们尝试从(1,1)出发，走到(n, m)
// dfs(x, y, have)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int n, m, g[N][N];
bool vis[N][N];
int ret = -0x3f3f3f3f;

int dx[] = {0, 1, -1}, dy[] = {1, 0, 0};

void dfs(int x, int y, int have){   
    if (x == n && y == m) {
        ret = max(ret, have);
        return ;
    }

    for (int i = 0; i < 3; i++){
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m) continue;
        if (vis[a][b]) continue;

        vis[a][b] = true;
        dfs(a, b, have + g[a][b]);
        vis[a][b] = false;
    }
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            scanf("%d", &g[i][j]);
        }

    vis[1][1] = true;
    dfs(1, 1, g[1][1]);

    cout << ret << '\n';

    return 0;
}

100pts

思考的关键点是：正难则反，递归+记忆化。从(n, m)开始缩小问题规模，缩小到(1, 1)。在缩小的过程中，利用记忆化。每一个点可以从左，从上，从下过来，有三种情况，当然，这三种情况需要是合法的，不能越界。

// 首先，我们尝试反着来，20pts

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10, INF = -0x3f3f3f3f;

int n, m, g[N][N];
bool vis[N][N];
int ret = -0x3f3f3f3f;
int mem[N][N];

int dx[] = {-1, 0, 1}, dy[] = {0, -1, 0};

void dfs(int x, int y, int have){   
    if (x == 1 && y == 1) {
        ret = max(ret, have);
        return ;
    }

    for (int i = 0; i < 3; i++){
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m) continue;
        if (vis[a][b]) continue;
        if (have + g[a][b] < mem[a][b]) continue;

        vis[a][b] = true;
        dfs(a, b, have + g[a][b]);
        vis[a][b] = false;
    }
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            scanf("%d", &g[i][j]);
            mem[i][j] = INF;
        }

    vis[n][m] = true;
    mem[n][m] = g[n][m];
    dfs(n, m, g[n][m]);

    cout << ret << '\n';

    return 0;
}

// 然后，我们不能再暴力了，引入三种情况讨论和记忆化。100pts

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e3 + 10;
const ll INF = -1e18;

// [0]从左侧来，[1]从上方来，[2]从下方来
ll f[N][N][3];
int n, m, g[N][N];

ll dfs(int x, int y, int from){ 
    if (x == 1 && y == 1) {
        return g[x][y];
    }

    ll &ret = f[x][y][from];
    if (ret != INF) return ret;

    if (from == 0) 
        if (y > 1) ret = max(ret, max(dfs(x, y-1, 0), max(dfs(x, y-1, 1), dfs(x, y-1, 2))) + g[x][y]);

    if (from == 1)
        if (x > 1) ret = max(ret, max(dfs(x-1, y, 0), dfs(x-1, y, 1)) + g[x][y]);

    if (from == 2)
        if (x < n) ret = max(ret, max(dfs(x+1, y, 0), dfs(x+1, y, 2)) + g[x][y]);

    return ret;

}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            scanf("%d", &g[i][j]);
            f[i][j][0] = f[i][j][1] = f[i][j][2] = INF;
        }

    // 正难则反
    cout << max(dfs(n, m, 0), dfs(n, m, 1)) << '\n';

    return 0;
}

// 记忆化得手后，尝试用循环的方式，实现dp
// 这里面有关键点，是阶段的划分，这个阶段是一列一列的，往右推。100pts

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e3 + 10;
const ll INF = -1e18;

// f[i][j][0]从左侧来 f[i][j][1]从上方来，f[i][j][2]从下方来
ll f[N][N][3];
int n, m, g[N][N];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            scanf("%d", &g[i][j]);
            f[i][j][0] = f[i][j][1] = f[i][j][2] = INF;
        }

    f[1][1][0] = f[1][1][1] = f[1][1][2] = g[1][1];
    for (int j = 1, i = 2; i <= n; i++) f[i][j][1] = f[i - 1][j][1] + g[i][j];

    for (int j = 2; j <= m; j++){
        for (int i = 1; i <= n; i++)
            f[i][j][0] = max(f[i][j][0], max(f[i][j-1][0], max(f[i][j-1][1], f[i][j-1][2])) + g[i][j]);

        for (int i = 2; i <= n; i++)
            f[i][j][1] = max(f[i][j][1], max(f[i-1][j][0], f[i-1][j][1]) + g[i][j]);

        for (int i = n - 1; i >= 1; i--)
            f[i][j][2] = max(f[i][j][2], max(f[i+1][j][0], f[i+1][j][2]) + g[i][j]);
    }

    ll ret = max(f[n][m][0], max(f[n][m][1], f[n][m][2]));
    cout << ret << '\n';

    return 0;
}

总结

考场上，打暴力，实测25pts，所以25分是要拿好的

思考记忆化，是一个靠谱的策略，多练

循环方式实现dp，就是dp技能成熟之后，打这个