链接:
https://www.acwing.com/problem/content/description/277/
题意:
给定一个 N*M 的矩阵A，每个格子中有一个整数。
现在需要找到两条从左上角 (1,1) 到右下角 (N,M) 的路径，路径上的每一步只能向右或向下走。
路径经过的格子中的数会被取走，两条路径可以经过同一个格子，但格子中的数 只能被取一次。
求取得的数之和最大是多少。
思路:
三角形Dp的加强版,可以枚举走的步长,和两个点的x坐标,y坐标可以推出来.
然后四种情况转移一下.
代码:
#include <bits/stdc++.h>
using namespace std;
int Map[60][60];
int Dp[200][60][60];
int n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
scanf("%d", &Map[i][j]);
}
Dp[0][1][1] = Map[1][1];
for (int len = 1;len <= n+m-2;len++)
{
for (int x1 = 1;x1 <= n;x1++)
{
int y1 = len-x1+2;
if (y1 < 1 || y1 > m)
continue;
for (int x2 = 1;x2 <= n;x2++)
{
int y2 = len-x2+2;
if (y2 < 1 || y2 > m)
continue;
if (x1 == x2)
{
Dp[len][x1][x2] = max(Dp[len][x1][x1], Dp[len-1][x1][x2]+Map[x1][y1]);
Dp[len][x1][x2] = max(Dp[len][x1][x1], Dp[len-1][x1-1][x2]+Map[x1][y1]);
Dp[len][x1][x2] = max(Dp[len][x1][x1], Dp[len-1][x1][x2-1]+Map[x1][y1]);
Dp[len][x1][x2] = max(Dp[len][x1][x1], Dp[len-1][x1-1][x2-1]+Map[x1][y1]);
}
else
{
Dp[len][x1][x2] = max(Dp[len][x1][x2], Dp[len-1][x1][x2]+Map[x1][y1]+Map[x2][y2]);
Dp[len][x1][x2] = max(Dp[len][x1][x2], Dp[len-1][x1-1][x2]+Map[x1][y1]+Map[x2][y2]);
Dp[len][x1][x2] = max(Dp[len][x1][x2], Dp[len-1][x1][x2-1]+Map[x1][y1]+Map[x2][y2]);
Dp[len][x1][x2] = max(Dp[len][x1][x2], Dp[len-1][x1-1][x2-1]+Map[x1][y1]+Map[x2][y2]);
}
}
}
}
printf("%d\n", Dp[n+m-2][n][n]);
return 0;
}