首页 > 代码库 > Codeforces_429_B

Codeforces_429_B

http://codeforces.com/problemset/problem/429/B

 

挺简单的题,先求出四个点到每一点的最大和,然后枚举每一点,取和最大值。

注意两条路相交的点有且只有一个,这点的数值不加。

 

#include<iostream>#include<algorithm>using namespace  std;int a[1005][1005];int s1[1005][1005] = {0},e1[1005][1005] = {0},s2[1005][1005] = {0},e2[1005][1005] = {0};int main(){    int n,m;    cin >> n >> m;    for(int i = 1;i <= n;i++)    {        for(int j = 1;j <= m;j++)   cin >> a[i][j];    }    s1[1][1] = a[1][1];    s2[n][1] = a[n][1];    e1[n][m] = a[n][m];    e2[1][m] = a[1][m];    for(int i = 2;i <= n;i++)    {        s1[i][1] += a[i][1]+s1[i-1][1];        e2[i][m] += a[i][m]+e2[i-1][m];    }    for(int i = n-1;i >= 1;i--)    {        s2[i][1] += a[i][1]+s2[i+1][1];        e1[i][m] += a[i][m]+e1[i+1][m];    }    for(int i = 2;i <= m;i++)    {        s1[1][i] += a[1][i]+s1[1][i-1];        s2[n][i] += a[n][i]+s2[n][i-1];    }    for(int i = m-1;i >= 1;i--)    {        e2[1][i] += a[1][i]+e2[1][i+1];        e1[n][i] += a[n][i]+e1[n][i+1];    }    for(int i = 2;i <= n;i++)    {        for(int j = 2;j <= m;j++)        {            s1[i][j] = max(s1[i-1][j]+a[i][j],s1[i][j-1]+a[i][j]);        }        for(int j = m-1;j >= 1;j--)        {            e2[i][j] = max(e2[i-1][j]+a[i][j],e2[i][j+1]+a[i][j]);        }    }    for(int i = n-1;i >= 1;i--)    {        for(int j = 2;j <= m;j++)        {            s2[i][j] = max(s2[i][j-1]+a[i][j],s2[i+1][j]+a[i][j]);        }        for(int j = m-1;j >= 1;j--)        {            e1[i][j] = max(e1[i][j+1]+a[i][j],e1[i+1][j]+a[i][j]);        }    }    int ans = 0;    for(int i = 2;i < n;i++)    {        for(int j = 2;j < m;j++)        {            ans = max(ans,s1[i-1][j]+s2[i][j-1]+e1[i+1][j]+e2[i][j+1]);            ans = max(ans,s1[i][j-1]+s2[i+1][j]+e1[i][j+1]+e2[i-1][j]);        }    }    cout << ans << endl;    return 0;}

 

Codeforces_429_B