走方格

· · 题解

下文中视 n,m 同阶。

Subtask1: O(n^4) 暴力枚举。

设 f_{i,j} 为从 (1,1) 走到 (i,j) 得分的最大值。

由于 (i,j) 只能由 (i-1,j),(i,j-1) 走来，显然有： f_{i,j} = max(f_{i-1,j},f_{i,j-1})+a_{i,j}

所以 O(n^2) 枚举权值变为 0 的点，每次再 O(n^2) dp 求出最大得分并取其最小值即可。

Subtask2: O(n^3)

还是考虑枚举权值变为 0 的点 (i,j)， 显然此时最大得分为不经过该点的最大得分与 经过该点的最大得分减去 a_{i,j} 的最大值。

关键是如何得出不经过该点的最大得分？

我们可以先考虑如何得出经过 (i,j) 的最大得分。

设 g(i,j) 为从 (n,m) 走到 (i,j) 得分的最大值。

同理易得：g_{i,j} =max(g_{i+1,j},g_{i,j+1})+a_{i,j}

显然经过 (i,j) 的最大得分为 f_{i,j}+g_{i,j}-a_{i,j}

由于只能向下或向右走，因此我们可以发现不经过 (i,j) 的路径一定是经过该点同行左边一点并向下走或同列上面一点并向右走，这样就不可能经过 (i,j) 了。

于是将 (i,j) 权值变为 0 时的最大得分为： \max (f_{i,j}+g_{i,j}- 2 \times a_{i,j} , \max( f_{x,j}+g_{x,j+1} ), \max( f_{i,y}+g_{i+1,y} ) ), x \in [1,i), y \in [1,j)

答案取其最小值即可。

Subtask3: O(n^2)

方法一：

发现 \max( f_{x,j}+g_{x,j+1} ) 和 \max( f_{i,y}+g_{i+1,y} ), x \in [1,i), y \in [1,j) 可以预处理出来。

设 F_{i,j,0} 为 \max( f_{i,y}+g_{i+1,y} )， F_{i,j,1} 为 \max( f_{x,j}+g_{x,j+1} )。

可得 F_{i,j,0} = \max(F_{i,j-1,0}, f_{i,j} + g_{i+1,j}),

答案即为： $\min( \max(f_{i,j}+g_{i,j}- 2 \times a_{i,j}, \max(F_{i,j-1,0}, F_{i-1,j,1})) )

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define G() Cr = getchar()
#define LL long long
int Xr, Fr; char Cr;
inline int rd() {
    Xr = 0, Fr = 1, G();
    while(Cr < '0' || Cr > '9') {if(Cr == '-') Fr = -1; G();}
    while(Cr >= '0' && Cr <= '9') Xr = (Xr<<1) + (Xr<<3) + (Cr&15), G();
    return Xr * Fr;
}
#define MAX_N 2005
int n, m;
LL va[MAX_N][MAX_N], f[MAX_N][MAX_N], g[MAX_N][MAX_N], F[MAX_N][MAX_N][2], ans = 1e18; // F[i][j][0] -> left
int main() { 
    n = rd(), m = rd();
    for( int i = 1; i <= n; i++)
        for( int j = 1; j <= m; j++)
            va[i][j] = rd();
    for( int i = 1; i <= n; i++ )
        for( int j = 1; j <= m; j++ )
            f[i][j] = va[i][j] + max(f[i-1][j],f[i][j-1]);
    for( int i = n; i >= 1; i-- )
        for( int j = m; j >= 1; j-- ) 
            g[i][j] = va[i][j] + max(g[i+1][j],g[i][j+1]);
    for( int i = 1; i <= n; i++ )
        for( int j = 1; j <= m; j++ )
            F[i][j][0] = max( F[i][j-1][0], f[i][j] + g[i+1][j]),
            F[i][j][1] = max( F[i-1][j][1], f[i][j] + g[i][j+1]),
            ans = min(ans, max( max( F[i][j-1][0], F[i-1][j][1]), f[i][j] + g[i][j] - 2 * va[i][j] ) );
    cout << ans;
}

方法二：

这次考虑走的步数，预处理出走 k 步时经过各点 (i,k-i) 时的最大得分及其橫坐标 i，以及经过各点的最大得分的次大值（可与最大值相同）。

最大得分显然都是 f_{n,m}，枚举权值变为 0 的点 (i,j) 时每次便判断 i 是不是走 i+j 步最大得分的横坐标，若不是，则最大得分就是 f_{n,m}， 即变该点权值不会影响答案；否则说明该点是最大得分路径上一点，则最大得分为其次大值和经过 (i,j) 的最大得分的最大值。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define G() Cr = getchar()
#define LL long long
int Xr, Fr; char Cr;
inline int rd() {
    Xr = 0, Fr = 1, G();
    while(Cr < '0' || Cr > '9') {if(Cr == '-') Fr = -1; G();}
    while(Cr >= '0' && Cr <= '9') Xr = (Xr<<1) + (Xr<<3) + (Cr&15), G();
    return Xr * Fr;
}
#define MAX_N 2005
int n, m;
LL va[MAX_N][MAX_N], f[MAX_N][MAX_N], g[MAX_N][MAX_N], F[MAX_N][MAX_N], G[4005][2], Gx[4005], ans = 1e18; // G[i][0] max G[i][1] 2th_max
int main() { 
    n = rd(), m = rd();
    for( int i = 1; i <= n; i++)
        for( int j = 1; j <= m; j++)
            va[i][j] = rd();
    for( int i = 1; i <= n; i++ )
        for( int j = 1; j <= m; j++ )
            f[i][j] = va[i][j] + max(f[i-1][j],f[i][j-1]);
    for( int i = n; i >= 1; i-- )
        for( int j = m; j >= 1; j-- ) 
            g[i][j] = va[i][j] + max(g[i+1][j],g[i][j+1]);
    for( int i = 2; i <= n + m; i++ )
        for( int k = max(1,i-m); k < min(i,n+1) ; k++ )
            if( f[k][i-k] + g[k][i-k] - va[k][i-k] > G[i][0] ) G[i][1] = G[i][0], G[i][0] = f[k][i-k] + g[k][i-k] - va[k][i-k], Gx[i] = k;
            else if( f[k][i-k] + g[k][i-k] - va[k][i-k] > G[i][1] ) G[i][1] = f[k][i-k] + g[k][i-k] - va[k][i-k];
    for( int i = 1; i <= n; i++ )
        for( int j = 1; j <= m; j++ ) {
            if( Gx[i+j] == i ) F[i][j] = max(G[i+j][0] - va[i][j], G[i+j][1] );
            else F[i][j] = G[i+j][0];
            ans = min(F[i][j],ans);
        }
    cout << ans;
}