ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
王梓豪 / 题目列表训练档案
导出

P1004　[NOIP 2000 提高组] 方格取数

来源：洛谷 ★ 1500

DP自评已掌握
本题活力0.51按难度、完成结果与训练证据估算

算法如山行则将至

查看原题王梓豪 的主页

题目描述

设有 $N \times N$ 的方格图（$N \le 9$），我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 $0$。如下图所示（见样例）：

某人从图的左上角的 $A$ 点出发，可以向下行走，也可以向右走，直到到达右下角的 $B$ 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 $0$）。

此人从 $A$ 点到 $B$ 点共走两次，试找出 $2$ 条这样的路径，使得取得的数之和最大。

代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 0))));
    vector<vector<int>> a(n + 1, vector<int>(n + 1, 0)); 
    int x, y, num;
    while (cin >> x >> y >> num) {
        if (x == 0 && y == 0 && num == 0) break;
        a[x][y] = num;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                int l = i + j - k;
                if (l < 1 || l > n) continue;
                int max_val = max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]),
                                  max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1]));

                dp[i][j][k][l] = max_val + a[i][j];
                if (i != k || j != l) {
                    dp[i][j][k][l] += a[k][l];
                }
            }
        }
    }
    cout << dp[n][n][n][n] << endl;
    return 0;
}