算法知识点: 线性DP

复杂度：

解题思路：

状态表示：f[k, i, j]表示两个人同时走了k步，第一个人在 (i, k - i) 处，第二个人在 (j, k - j)处的所有走法的最大分值。

状态计算：按照最后一步两个人的走法分成四种情况：

  • 两个人同时向右走，最大分值是f[k - 1, i, j] + score(k, i, j)；
  • 第一个人向右走，第二个人向下走，最大分值是f[k - 1, i, j - 1] + score(k, i, j)；
  • 第一个人向下走，第二个人向右走，最大分值是f[k - 1, i - 1, j] + score(k, i, j)；
  • 两个人同时向下走，最大分值是f[k - 1, i - 1, j - 1] + score(k, i, j)；

其中如果两人在相同格子，则score(k, i, j)等于这个格子的分值；否则等于两个格子的分值之和。

C++ 代码： 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 55;

int n, m;
int g[N][N];
int f[N * 2][N][N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &g[i][j]);

    for (int k = 2; k <= n + m; k++)
        for (int i = max(1, k - m); i <= n && i < k; i++)
            for (int j = max(1, k - m); j <= n && j < k; j++)
                for (int a = 0; a <= 1; a++)
                    for (int b = 0; b <= 1; b++)
                    {
                        int t = g[i][k - i];
                        if (i != j) t += g[j][k - j];
                        f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
                    }

    printf("%d\n", f[n + m][n][n]);

    return 0;
}


另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ