[NOIP2008]传纸条

解题思路:

dp[k][i][j] 表示两条路径总步数为 k 时：

第一条路径位于 (i, k-i+1)

第二条路径位于 (j, k-j+1)

此时的最大好心值总和

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int g[N][N], dp[N*2][N][N], m, n;

int main()
{
    cin >> m >> n;  // 输入矩阵的行数m和列数n
    
    // 读取矩阵中每个位置的好心值
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            cin >> g[i][j];
    
    // 初始化动态规划数组，dp[k][i][j]表示两条路径总步数为k时：
    // 第一条路径在(i, k-i+1)位置，第二条路径在(j, k-j+1)位置的最大好心值和
    memset(dp, 0, sizeof(dp));
    
    // 总步数k的范围：从2到m+n-1
    // 因为从(1,1)到(m,n)至少需要m+n-2步，加上起点的0步，总步数为m+n-1
    for(int k = 2; k <= m + n - 1; ++k)
        for(int i = 1; i <= m; ++i)          // 第一条路径的行坐标
            for(int j = 1; j <= m; ++j) {    // 第二条路径的行坐标
                // 根据总步数k和行坐标i/j，计算对应的列坐标
                int c1 = k - i + 1;
                int c2 = k - j + 1;
                
                // 检查列坐标是否在有效范围内，超出则跳过
                if(c1 < 1 || c1 > n || c2 < 1 || c2 > n) continue;
                
                // 当前位置的好心值之和，若两条路径重合则只算一次
                int t = g[i][c1];
                if(i != j)
                    t += g[j][c2];
                
                // 状态转移：从四个可能的上一步状态中取最大值
                dp[k][i][j] = max({
                    dp[k-1][i-1][j],    // 第一条路径向下，第二条路径向右
                    dp[k-1][i][j-1],    // 第一条路径向右，第二条路径向下
                    dp[k-1][i-1][j-1],  // 两条路径都向下
                    dp[k-1][i][j]       // 两条路径都向右
                }) + t;
            }
    
    // 输出最终结果：当总步数为m+n-1时，两条路径都到达终点(m,n)的最大好心值和
    cout << dp[m + n - 1][m][m] << endl;
    
    return 0;
}