本文共 1597 字，大约阅读时间需要 5 分钟。

题意

给一个矩阵每个位置一个value，求从左上角到右下角和左下角到右上角value和，相交的地方value不计，问和最大多少

AC

• 分别求出每个点四个方向的value和
• 每个点可以有四种走法，满足情况的只有两种（可画图模拟）

#include 
   
    #define ll long long#define N 100005#define mem(a, b) memset(a, b, sizeof(a))#define P pair
    
     using namespace std;int dp[1005][1005][4];int a[1005][1005];int main() {    // freopen("in.txt", "r", stdin);    int r, c;    while(cin >> r >> c) {        mem(dp, 0);        for (int i = 1; i <= r; ++i) {            for (int j = 1; j <= c; ++j) {                cin >> a[i][j];            }        }        for (int i = 1; i <= r; ++i) {            // 右下            for (int j = 1; j <= c; ++j) {                dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]) + a[i][j];            }            // 左下            for (int j  = c; j >= 1; --j) {                dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j + 1][1]) + a[i][j];            }        }        for (int i = r; i >= 1; --i) {            // 右上            for (int j = 1; j <= c; ++j) {                dp[i][j][2] = max(dp[i][j - 1][2], dp[i + 1][j][2]) + a[i][j];            }            // 左上            for (int j = c; j >= 1; --j) {                dp[i][j][3] = max(dp[i + 1][j][3], dp[i][j + 1][3]) + a[i][j];            }        }        int ans = 0;        for (int i = 2; i < r; ++i) {            for (int j = 2; j < c; ++j) {                ans = max(ans, dp[i - 1][j][0] + dp[i + 1][j][3] + dp[i][j - 1][2] + dp[i][j + 1][1]);                ans = max(ans, dp[i - 1][j][1] + dp[i + 1][j][2] + dp[i][j - 1][0] + dp[i][j + 1][3]);            }        }        cout << ans << endl;    }    return 0;}
    
   

转载地址：http://gzprf.baihongyu.com/