【每日一题】9月9日题目精讲-Working out

其实这个倒着想就行，从一个点出发到四个角的距离最大，正好还不用处理自己本身的值，如果正常思维的话会很麻烦并且不会写。。。
一共两种情况，ans两种判断方式。
设四个数组分别表示到四个角的最大距离

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
//#include<bits/stdc++.h>
typedef long long ll;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)        //快速幂模板
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}
///////////////////////////////////////////////////////////
int a[1005][1005];
int dp1[1005][1005]; int dp2[1005][1005];
int dp3[1005][1005]; int dp4[1005][1005];
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];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <=m; j++)
            dp1[i][j] = max(dp1[i - 1][j], dp1[i][j-1]) + a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 1; j--)
            dp2[i][j] = max(dp2[i - 1][j], dp2[i][j + 1]) + a[i][j];
    for (int i = n; i >= 1; i--)
        for (int j = m; j >= 1; j--)
            dp3[i][j] = max(dp3[i + 1][j], dp3[i][j + 1]) + a[i][j];
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            dp4[i][j] = max(dp4[i + 1][j], dp4[i][j-1]) + a[i][j];
    //四个数组分别代表枚举的中间点到四个对角的最大距离
    int ans = 0;
    for (int i = 2; i < n; ++i)
        for (int j = 2; j < m; ++j)
            ans = max(ans, dp1[i - 1][j] + dp3[i + 1][j] + dp2[i][j + 1] + dp4[i][j - 1]),
            ans = max(ans, dp1[i][j - 1] + dp3[i][j + 1] + dp2[i - 1][j] + dp4[i + 1][j]);
    cout << ans << endl;
    return 0;
}

总的来说还行，不像别的dp那么难想，但是也不是很容易。。。