NOIP 2000 提高组 洛谷1004题（方格取数）解题思路与C++代码解析

一、题目描述

    简要描述题目：例如，在一个n×n的方格图中，每个格子包含一个正整数。需要选择两条从左上角到右下角的路径，路径可重复经过格子，但两条路径除起点和终点外不能相交。求两条路径数字和的最大值。

二 、代码解析（带注释）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 15; // 网格最大维度
int g[N][N], f[N*2][N][N]; // g存储原网格，f为动态规划数组

int main() {
    int n, x, y, v; // n为网格大小，x,y,v为输入的坐标和值
    cin >> n; // 读取网格大小

    // 输入网格数据（注意：用户代码可能未处理EOF情况，但洛谷题目通常无影响）
    while((cin >> x >> y >> v) && (x || y || v)) {
        g[x][y] = v; // 将数据存入g数组
    }

    // 初始化动态规划数组（除起点外，其余状态设为负无穷）
    memset(f, -0x3f, sizeof f);
    f[0][1][1] = g[1][1]; // 起点状态：两条路径均从(1,1)出发，和为g[1][1]

    // 动态规划主循环
    for(int k = 1; k <= 2*n-2; ++k) { // k为总步数（两条路径共走2n-2步）
        for(int i = 1; i <= min(n, k+1); ++i) { // 第一条路径的行坐标
            for(int j = 1; j <= min(n, k+1); ++j) { // 第二条路径的列坐标
                int &val = f[k][i][j]; // 引用简化代码
                val = max({
                    f[k-1][i][j],       // 路径1不动，路径2移动
                    f[k-1][i-1][j],     // 路径1向下，路径2不动
                    f[k-1][i][j-1],     // 路径1不动，路径2向右
                    f[k-1][i-1][j-1]   // 路径1向下，路径2向右
                });
                if(i == j) val += g[i][k+2-i]; // 重复点：两条路径同时移动，加一次数字
                else val += g[i][k+2-i] + g[j][k+2-j]; // 非重复点：两条路径分别移动，加两次数字
            }
        }
    }

    // 输出结果
    cout << f[2*n-2][n][n] << endl; // 两条路径均到达右下角时的最大和
    return 0;
}