求从N*M矩形的左上角到右下角两条路径的最大值
下面的代码中:
a[i][j]代表:任意一点的路程
b[i][j][k][l]代表:一点在i,j处,另一点在k,l处时所能取得的最大值
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int a[55][55];
int b[55][55][55][55];
int main ()
{
int n,m;
cin >> n >> m;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
cin >> a[i][j];
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<=n;k++)
for (int l=1;l<=m;l++)
{
if(i!=k||j!=l||(i==n&&j==m&&k==n&&l==m))
{
b[i][j][k][l]=max(b[i][j][k][l],b[i-1][j][k-1][l]);
b[i][j][k][l]=max(b[i][j][k][l],b[i-1][j][k][l-1]);
b[i][j][k][l]=max(b[i][j][k][l],b[i][j-1][k-1][l]);
b[i][j][k][l]=max(b[i][j][k][l],b[i][j-1][k][l-1]);
b[i][j][k][l]+=a[i][j]+a[k][l];
}
}
cout << b[n][m][n][m] << endl;
return 0;
}



京公网安备 11010502036488号