2023.10.1记录

被NOIP提高组的题暴虐。

[NOIP2000 提高组] 方格取数

NOIP2000 提高组] 方格取数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意

从一个\(n\times n\)的矩阵的左上角走到右下角，只能往右边和下边走，选择两条路，把这两条路经过的单位的数字取走，每个单位的数字只能取一次，求最大能取走的数字的总和。

思路

搜索，两条路一起走，每次有四种情况。但是复杂度为\(4^{2n}\)，肯定会超时，所以要用记忆化搜索。

代码

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int mat[10][10] = {0};
    while(true) {
        int x, y, z;
        cin >> x >> y >> z;
        if(!x && !y && !z) {
            break;
        }
        mat[x][y] = z;
    }

    int f[10][10][10][10] = {0};
    memset(f, -1, sizeof f);

    auto dfs = [&](auto self, int x1, int y1, int x2, int y2) ->i64 {
        if(f[x1][y1][x2][y2] != -1) {
            return f[x1][y1][x2][y2];
        }
        if(x1 == n && y1 == n) {
            return 0;
        }

        i64 res = 0;
        if(x1 < n && x2 < n) {
            res = max(res, self(self, x1 + 1, y1, x2 + 1, y2) + mat[x1 + 1][y1] + mat[x2 + 1][y2] - mat[x2 + 1][y2] * (x1 + 1 == x2 + 1 && y1 == y2));
        }
        if(y1 < n && y2 < n) {
            res = max(res, self(self, x1, y1 + 1, x2, y2 + 1) + mat[x1][y1 + 1] + mat[x2][y2 + 1] - mat[x2][y2 + 1] * (y1 + 1 == y2 + 1 && x1 == x2));
        }
        if(y1 < n && x2 < n) {
            res = max(res, self(self, x1, y1 + 1, x2 + 1, y2) + mat[x1][y1 + 1] + mat[x2 + 1][y2] - mat[x2 + 1][y2] * (x1 == x2 + 1 && y1 + 1 == y2));
        }
        if(x1 < n && y2 < n) {
            res = max(res, self(self, x1 + 1, y1, x2, y2 + 1) + mat[x1 + 1][y1] + mat[x2][y2 + 1] - mat[x2][y2 + 1] * (x1 + 1 == x2 && y1 == y2 + 1));
        }
        return f[x1][y1][x2][y2] = res;
    };

    cout << dfs(dfs, 1, 1, 1, 1) + mat[1][1] << "\n";

    return 0;
}