本文共 1747 字，大约阅读时间需要 5 分钟。

在这个问题中，我们需要计算两个从对角线的两个端点出发的移动者在n×n网格中相遇时的总分。第一个移动者从(1,1)出发，只能向右或向下移动；第二个移动者从(n,n)出发，只能向左或向上移动。每当他们走到同一个格子时，只累加一次该格子的分数。

动态规划的思路

我们可以使用动态规划来解决这个问题。定义状态dp[i][j][k]为第一个移动者走了i步，第二个移动者走了k步，此时第一个移动者位于第j行，第二个移动者位于第k行。由于每一步移动都会改变行或列的位置，且每个移动者的移动方向有限制，我们可以通过状态转移来计算最终的总分。

状态转移方程

对于每一个状态i（即两人都走了i步），我们需要考虑第一个移动者和第二个移动者在i-1步时的可能位置，然后计算他们移动到当前位置的最大总分。

具体来说，第一个移动者在第i步可以从：

• 左边(i-1, j)
• 上边(j, i-1)
• 左上角(i-1, j-1)

第二个移动者在第i步可以从：

• 上边(i-1, k)
• 左边(k, i-1)
• 左上角(i-1, k-1)

对于每一种可能的转移，我们计算对应的分数，并将其与当前状态dp[i][j][k]进行比较，取最大值作为新的状态值。

代码实现

#include 
   
    
using namespace std;
typedef long long ll;
const int maxn = 305;
const int inf = 0x3f3f3f3f;
int n, dp[maxn][maxn][maxn];
ll a[maxn][maxn];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    memset(dp, -inf, sizeof(dp));
    dp[1][1][1] = a[1][1];
    
    for (int i = 1; i <= 2 * n - 1; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= n; ++k) {
                if (j > i || k > i) continue;
                if (j < 1 || k < 1) continue;
                
                int temp = a[j][i - j + 1] + (j != k ? a[k][i - k + 1] : 0);
                dp[i][j][k] = max(
                    dp[i-1][j][k] + temp,
                    dp[i-1][j-1][k] + temp,
                    dp[i-1][j][k-1] + temp,
                    dp[i-1][j-1][k-1] + temp
                );
            }
        }
    }
    cout << dp[2 * n - 1][n][n] << endl;
}
   

代码解释

这种方法通过动态规划有效地计算了两移动者的路径分数之和，确保了所有可能的路径都被考虑进去了。

转载地址：http://leewz.baihongyu.com/