#include "grid.h"
#include <algorithm>
#include <climits>
using namespace std;
constexpr int MAXN = 500003;

long long max_profit(int N, int M, int C, vector<vector<int>> A)
{
    static long long lhsdp[2][2][MAXN], rhsdp[2][2][MAXN];
    long long lasdp = 0;
    for (int i = 0, o = 0; i < N; ++i, o ^= 1)
    {
        for (int j = 0; j < M; ++j)
        {
            lasdp = lhsdp[o][0][j] = lhsdp[o][1][j] = LLONG_MIN, rhsdp[o][0][j] = rhsdp[o][1][j] = LLONG_MAX;
            if (i > 0)
            {
                lhsdp[o][0][j] = max(lhsdp[o][0][j], lhsdp[o ^ 1][0][j]);
                rhsdp[o][0][j] = min(rhsdp[o][0][j], rhsdp[o ^ 1][0][j]);
                lasdp = max({lasdp, lhsdp[o ^ 1][0][j] - A[i][j], A[i][j] - rhsdp[o ^ 1][0][j]});
            }
            if (j > 0)
            {
                lhsdp[o][1][j] = max(lhsdp[o][1][j], lhsdp[o][1][j - 1]);
                rhsdp[o][1][j] = min(rhsdp[o][1][j], rhsdp[o][1][j - 1]);
                lasdp = max({lasdp, lhsdp[o][1][j - 1] - A[i][j], A[i][j] - rhsdp[o][1][j - 1]});
            }
            if (!i && !j)
                lasdp = 0;
            lhsdp[o][0][j] = max(lhsdp[o][0][j], lasdp + A[i][j] - C);
            lhsdp[o][1][j] = max(lhsdp[o][1][j], lasdp + A[i][j] - C);
            rhsdp[o][0][j] = min(rhsdp[o][0][j], -lasdp + A[i][j] + C);
            rhsdp[o][1][j] = min(rhsdp[o][1][j], -lasdp + A[i][j] + C);
        }
    }
    return lasdp;
}

前言

黄题难度是对的。

暴力：一眼 dp

根据题目标签我们很容易发现应该用 dp 做，所以初见直接交了一发暴力。 :::error[24 pts]

#include<vector>
#include<algorithm>
#include<cmath>
using std::vector;
using std::max;
long long max_profit(int N, int M, int C, std::vector<std::vector<int>> A)
{
    vector<vector<int> > dp=vector<vector<int> >(N,vector<int>(M,-1e8));
    auto abs=[](const int x){return x<0?-x:x;};
    auto f=[&](int x_1,int y_1,int x_2,int y_2)->int
    {
        return abs(A[x_1][y_1]-A[x_2][y_2])-C;
    };
    dp[0][0]=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            for(int d=1;d<=i;d++)
            {
                dp[i][j]=max(dp[i][j],dp[i-d][j]+f(i-d,j,i,j));
            }
            for(int d=1;d<=j;d++)
            {
                dp[i][j]=max(dp[i][j],dp[i][j-d]+f(i,j-d,i,j));
            }
        }
    return dp[N-1][M-1];
}

:::

状态转移方程是：

优化

当 $A_{x,y}>A_{x',y'}$ 时，$A_{x,y}$ 越大越好；
当 $A_{x,y}<A_{x',y'}$ 时，$-A_{x,y}$ 越大越好。

考虑对于每一行或每一列，分别维护一个位置使此位置 $(A_{x,y})$ 的最值 $+dp_{x,y}$ 的值在当前行或列最大。

此时，对每一格更新的复杂度为 $O(1)$，总复杂度为 $O(NM)$。

:::success[100 pts]

#include<vector>
#include<algorithm>
#include<cmath>
#define jiaohu 1
#if !jiaohu
#include<iostream>
using std::cout;
using std::endl;
#endif
using std::vector;
using std::max;
using ll=long long;
long long max_profit(int N, int M, int C, std::vector<std::vector<int>> A)
{
    vector<vector<ll> > dp=vector<vector<ll> >(N,vector<ll>(M,-1e9));
    vector<int>hang_max(N,0),hang_min(N,0),col_min(M,0),col_max(M,0);
    auto abs=[](const int x){return x<0?-x:x;};
    auto f=[&](const int &old_ge,const int &new_ge)->int
    {
        return abs(old_ge-new_ge)-C;
    };
    dp[0][0]=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            dp[i][j]=max(dp[i][j],
                max(
                max(dp[i][hang_max[i]]+f(A[i][hang_max[i]],A[i][j]),
                    dp[i][hang_min[i]]+f(A[i][hang_min[i]],A[i][j])),
                max(dp[col_max[j]][j]+f(A[col_max[j]][j],A[i][j]),
                    dp[col_min[j]][j]+f(A[col_min[j]][j],A[i][j])))
                         );
            if(A[i][hang_max[i]]+dp[i][hang_max[i]]<A[i][j]+dp[i][j])hang_max[i]=j;
            if(-A[i][hang_min[i]]+dp[i][hang_min[i]]<-A[i][j]+dp[i][j])hang_min[i]=j;
            if(A[col_max[j]][j] +dp[col_max[j]][j] <A[i][j]+dp[i][j]) col_max[j]=i;
            if(-A[col_min[j]][j] +dp[col_min[j]][j] <-A[i][j]+dp[i][j]) col_min[j]=i;
            //cout<<i<<' '<<j<<' '<<hang_min[i]<<' '<<dp[i][j]<<endl;
        }
    return dp[N-1][M-1];
}
#if !jiaohu
using std::vector;
using std::cin;
using std::cout;
int main()
{
    int N,M,C;
    cin>>N>>M>>C;
    vector<vector<int>>A(N,vector<int>(M,0));
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
            cin>>A[i][j];
    }
    cout<<max_profit(N,M,C,A);
    return 0;
}
#endif

:::

追加内容

一定要使用 64 位存储数据，并且初始化极小值，不然会 WA。