[NOIP2008 提高组] 传纸条

#include <bits/stdc++.h>
using namespace std;
int m, n;
int a[55][55];
// f[i][j][ii][jj] 第一个人走到 (i,j)，第二个人走到 (ii,jj) 的最大路径和
int f[55][55][55][55];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            for (int ii = 1; ii <= m; ii++)
                for (int jj = 1; jj <= n; jj++)
                {
                    f[i][j][ii][jj] = 0;
                    if (i == ii && j == jj && !(i == m && j == n))
                        continue;
                    f[i][j][ii][jj] = max(f[i][j][ii][jj], f[i - 1][j][ii - 1][jj]);
                    f[i][j][ii][jj] = max(f[i][j][ii][jj], f[i - 1][j][ii][jj - 1]);
                    f[i][j][ii][jj] = max(f[i][j][ii][jj], f[i][j - 1][ii - 1][jj]);
                    f[i][j][ii][jj] = max(f[i][j][ii][jj], f[i][j - 1][ii][jj - 1]);
                    f[i][j][ii][jj] += a[i][j] + a[ii][jj];
                }
    cout << f[m][n][m][n];
    return 0;
}