合肥工业大学oj p1012

时间:2023-11-10 08:54:07
#include <iostream>
#include <cstring>
#define maxn 5 + 2
using namespace std; int m, n, G[maxn][maxn], dp[maxn][maxn][maxn][maxn]; int main()
{
while (cin >> m >> n && m && n)
{
memset(G, , sizeof(G));
memset(dp, , sizeof(dp));
for (int i = ; i <= m; ++i)
for (int j = ; j <= n; ++j)
cin >> G[i][j]; for (int i = ; i <= n; ++i)
for (int j = ; j <= m; ++j)
for (int k = ; k <= n; ++k)
{
int l = i + j - k;
if (l >= )
dp[i][j][k][l] = G[i][j] + G[k][l] + max(max(dp[i - ][j][k - ][l], dp[i - ][j][k][l - ]), max(dp[i][j - ][k - ][l], dp[i][j - ][k][l - ]));
else continue; if(i == k && j == l)
dp[i][j][k][l] -= G[i][j];
} cout << dp[n][m][n][m] << endl;
} return ;
}