Codeforces 429B. Working out

題目連結:http://codeforces.com/problemset/problem/429/B

題意:給了一個nxm的矩陣,A從(1,1)出發,每次隻能走相鄰的右邊或者下邊的格子走到(n,m)停止.B從(n,1)出發,每次隻能走相鄰的右邊或者上邊的格子,走到(1,m)停止,兩人的路線隻能交于一個格子,除相交的格子外,求兩人路線上其他格子總和的最大值

分析:動态規劃.通過遞推求出分别以左上角,左下角,右上角,右下角為出發點到每一個個格子的距離和的最大值.注意右上角和右下角分别和左下角,左上角對應,是一個逆過程.還有一個坑點就是邊界沒有意義,要賦予極小值.我們枚舉每個格子的上下左右對應的兩種可能情況(注意不能是到某個格子的距離和再減去該格子的四倍,因為這樣有可能兩個人的路線相交)

代碼:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1010;
int mp[maxn][maxn];
ll dp1[maxn][maxn],dp2[maxn][maxn],dp3[maxn][maxn],dp4[maxn][maxn];
//dp1 left up dp2 left down dp3 right up dp4 right down
const int INF = 0x3f3f3f3f;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf("%d",&mp[i][j]);
        }
    }
    for(int i = 1; i <= m; i++)
        dp1[1][i] = dp1[1][i - 1] + mp[1][i];
    for(int i = 2; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(j == 1)dp1[i][j] = dp1[i - 1][j] + mp[i][j];
            else dp1[i][j] = max(dp1[i - 1][j],dp1[i][j - 1]) + mp[i][j];
        }
    }
    for(int i = 1; i <= m; i++)
        dp2[n][i] = dp2[n][i - 1] + mp[n][i];
    for(int i = n - 1; i >= 1; i--)
    {
        for(int j = 1; j <= m; j++)
        {
            if(j == 1)dp2[i][j] = dp2[i + 1][j] + mp[i][j];
            else dp2[i][j] = max(dp2[i + 1][j],dp2[i][j - 1])+ mp[i][j];
        }
    }
    for(int i = m; i >= 1; i--)
        dp3[1][i] = dp3[1][i + 1] + mp[1][i];
    for(int i = 2; i <= n; i++)
    {
        for(int j = m; j >= 1; j--)
        {
            if(j == m)dp3[i][j] = dp3[i - 1][j] + mp[i][j];
            else dp3[i][j] = max(dp3[i - 1][j],dp3[i][j + 1]) + mp[i][j];
        }
    }
    for(int i = m; i >= 1; i--)
        dp4[n][i] = dp4[n][i + 1] + mp[n][i];
    for(int i = n - 1; i >= 1; i--)
    {
        for(int j = m; j >= 1; j--)
        {
            if(j == m)dp4[i][j] = dp4[i + 1][j] + mp[i][j];
            else dp4[i][j] = max(dp4[i + 1][j],dp4[i][j + 1]) + mp[i][j];
        }
    }
    ll maxx = 0;
//    for(int i = 1; i <= n; i++)
//    {
//        for(int j = 1; j <= m; j++)
//        {
//            printf("%lld,%lld,%lld,%lld\n",dp1[i][j],dp2[i][j],dp3[i][j],dp4[i][j]);
//        }
//    }
    for(int i = 1; i <= n; i++)
    {
        dp1[i][0] = dp2[i][0] = dp3[i][0] = dp4[i][0] = -INF;
        dp1[i][m + 1] = dp2[i][m + 1] = dp3[i][m + 1] = dp4[i][m + 1] = -INF;
    }
    for(int i = 1; i <= m; i++)
    {
        dp1[0][i] = dp2[0][i] = dp3[0][i] = dp4[0][i] = -INF;
        dp1[n + 1][i] = dp2[n + 1][i] = dp3[n + 1][i] = dp4[n + 1][i] = -INF;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            ll ans = dp1[i][j - 1]+dp2[i + 1][j]+dp3[i - 1][j]+dp4[i][j + 1];
            maxx = max(maxx,ans);
            ans = dp1[i - 1][j] + dp2[i][j - 1] + dp3[i][j + 1] + dp4[i + 1][j];
            maxx = max(maxx,ans);
        }
    }
    cout<<maxx<<endl;
    return 0;
}