计蒜客 T2091 传纸条

题目链接：计蒜客 T2091 传纸条

题目大意：

题解：
由题意可知两路不会相交，设(dp[i][j][k])表示下面的那条路走到((i,j))，上面那条路走到((k, i+j-k))时好感程度的最大值，则状态转移方程为：

[dp[i][j][k] = max{dp[i - 1][j][k - 1], dp[i - 1][j][k],dp[i][j - 1][k - 1], dp[i][j - 1][k]}+a[i][j] + a[k][i + j - k],i eq k ]

由于(i eq k)，所以答案不能直接输出(dp[n][m][n])，因为右下角的好感程度一定为(0)，所以输出右下角的上一步(dp[n][m-1][n-1])。

#include <iostream>
using namespace std;

int dp[100][100][100], n, m, a[51][51];

int max_4(int a, int b, int c, int d) { return max(a, max(b, max(c, d))); }

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    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 < i; ++k) {
                if (i != k) {
                    dp[i][j][k] = max_4(dp[i - 1][j][k - 1], dp[i - 1][j][k], dp[i][j - 1][k - 1], dp[i][j - 1][k]) + a[i][j] + a[k][i + j - k];
                }
            }
        }
    }
    cout << dp[n][m - 1][n - 1];
    return 0;
}