UESTC 1651 Uestc的命運之旅

題目連結：​​http://acm.uestc.edu.cn/#/problem/show/1651​​

題意：

為了迎接大學的評教工作，Uestc迎來了很多專家。

為了Uestc的榮譽，我們當然是想盡可能多的增加專家的好感度。

然而，Uestc并不是完美無暇的，是以現在我們需要給專家們規劃出一條最能增加好感度的路線。 但是最近大家都比較忙，是以你的輔導員将這個艱巨的工作交給了你的室友。Uestc可以被看成是n×m

的矩陣A。專家團隊有兩個，一個從(1,1)點出發，需要到達(n,m)點。隻能從(i,j)走到(i+1,j)或(i,j+1)。 另一個從(n,1)出發, 需要到達(1,m)點。隻能從(i,j)走到(i,j+1)或(i−1,j)。

專家們會在點(i,j)獲得Aij的好感度。但是當兩路專家相遇時，他們會交換一下各自的意見，然後會發現這個學校女生太少了。是以他們不會獲得在這個點應得的好感度。幸運的是，在整個行程中， 兩路專家的路徑隻有一個格子是重合的。你的室友并不能勝任這個困難的工作，是以他帶着他的問題找到了聰明的你。

解法：直接預處理出從四個角到每個點的最大好感度，然後枚舉在哪個點相遇，更新答案即可。

注意有2種情況

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n, m, ans, a[maxn][maxn], dp[4][maxn][maxn];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            scanf("%d",&a[i][j]);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            dp[0][i][j]=max(dp[0][i][j],dp[0][i-1][j]+a[i][j]);
            dp[0][i][j]=max(dp[0][i][j],dp[0][i][j-1]+a[i][j]);
        }
    }
    for(int i=n; i>=1; i--){
        for(int j=1; j<=m; j++){
            dp[1][i][j]=max(dp[1][i][j],dp[1][i+1][j]+a[i][j]);
            dp[1][i][j]=max(dp[1][i][j],dp[1][i][j-1]+a[i][j]);
        }
    }
    for(int i=n; i>=1; i--){
        for(int j=m; j>=1; j--){
            dp[2][i][j]=max(dp[2][i][j], dp[2][i+1][j]+a[i][j]);
            dp[2][i][j]=max(dp[2][i][j], dp[2][i][j+1]+a[i][j]);
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=m; j>=1; j--){
            dp[3][i][j]=max(dp[3][i][j],dp[3][i-1][j]+a[i][j]);
            dp[3][i][j]=max(dp[3][i][j],dp[3][i][j+1]+a[i][j]);
        }
    }
    for(int i=2; i<n; i++){
        for(int j=2; j<m; j++){
            ans = max(ans, dp[0][i-1][j]+dp[2][i+1][j]+dp[1][i][j-1]+dp[3][i][j+1]);
            ans = max(ans, dp[0][i][j-1]+dp[2][i][j+1]+dp[1][i+1][j]+dp[3][i-1][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}