CodeForces - 429B Working out 簡單DP

Working out CodeForces - 429B

一個 n × m n\times m n×m 的矩陣 a a a ， a [ i ] [ j ] a[i][j] a[i][j] 表示 i i i 行 j j j 列可以燃燒的卡路裡，第一個人從 a [ 1 ] [ 1 ] a[1][1] a[1][1] 開始，到 a [ n ] [ m ] a[n][m] a[n][m] 結束，選擇 a [ i ] [ j ] a[i][j] a[i][j] 之後，他可以繼續選擇 a [ i + 1 ] [ j ] a[i+1][j] a[i+1][j] 或 a [ i ] [ j + 1 ] a[i][j+1] a[i][j+1] ，第二個人從 a [ n ] [ 1 ] a[n][1] a[n][1] 開始，到 a [ 1 ] [ m ] a[1][m] a[1][m] 結束，選擇 a [ i ] [ j ] a[i][j] a[i][j] 之後可以繼續選擇 a [ i ] [ j + 1 ] a[i][j+1] a[i][j+1] 或 a [ i − 1 ] [ j ] a[i-1][j] a[i−1][j]。

額外要求是他們必須在中間的某個格子裡相遇一次，在相遇的格子中，兩個人都不會燃燒卡路裡。當其中有一個到達目的地時就開始計算總收益（總共燃燒的卡路裡），問最大是多少？

用 f 1 [ i ] [ j ] , f 2 [ i ] [ j ] , f 3 [ i ] [ j ] , f 4 [ i ] [ j ] f_1[i][j],f_2[i][j],f_3[i][j],f_4[i][j] f1​[i][j],f2​[i][j],f3​[i][j],f4​[i][j] 分别表示從四個角 ( 1 , 1 ) (1,1) (1,1) 到 ( i , j ) (i,j) (i,j) 的最大值，從 ( i , j ) (i,j) (i,j) 到 ( n , m ) (n,m) (n,m) 的最大值，從 ( n , 1 ) (n,1) (n,1) 到 ( i , j ) (i,j) (i,j) 的最大值，從 ( i , j ) (i,j) (i,j) 到 ( 1 , m ) (1,m) (1,m) 的最大值，然後枚舉相遇點 ( i , j ) (i,j) (i,j) 即可。

f 1 [ i ] [ j ] = max ⁡ { f 1 [ i ] [ j − 1 ] , f 1 [ i − 1 ] [ j ] } + a [ i ] [ j ] f 2 [ i ] [ j ] = max ⁡ { f 2 [ i ] [ j + 1 ] , f 2 [ i + 1 ] [ j ] } + a [ i ] [ j ] f 3 [ i ] [ j ] = max ⁡ { f 3 [ i ] [ j − 1 ] , f 3 [ i + 1 ] [ j ] } + a [ i ] [ j ] f 4 [ i ] [ j ] = max ⁡ { f 4 [ i ] [ j + 1 ] , f 4 [ i − 1 ] [ j ] } + a [ i ] [ j ] \begin{aligned} f_1[i][j]&=\max\{f_1[i][j-1],f_1[i-1][j]\}+a[i][j]\\ f_2[i][j]&=\max\{f_2[i][j+1],f_2[i+1][j]\}+a[i][j]\\ f_3[i][j]&=\max\{f_3[i][j-1],f_3[i+1][j]\}+a[i][j]\\ f_4[i][j]&=\max\{f_4[i][j+1],f_4[i-1][j]\}+a[i][j]\\ \end{aligned} f1​[i][j]f2​[i][j]f3​[i][j]f4​[i][j]​=max{f1​[i][j−1],f1​[i−1][j]}+a[i][j]=max{f2​[i][j+1],f2​[i+1][j]}+a[i][j]=max{f3​[i][j−1],f3​[i+1][j]}+a[i][j]=max{f4​[i][j+1],f4​[i−1][j]}+a[i][j]​

代碼如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
//#define WINE
#define N 1005
using namespace std;
int n,m,a[N][N],f1[N][N],f2[N][N],f3[N][N],f4[N][N],res;
int main(){
#ifdef WINE
    freopen("data.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f1[i][j]=max(f1[i][j-1],f1[i-1][j])+a[i][j];
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--)
            f2[i][j]=max(f2[i][j+1],f2[i+1][j])+a[i][j];
    for(int i=n;i>=1;i--)
        for(int j=1;j<=m;j++)
            f3[i][j]=max(f3[i][j-1],f3[i+1][j])+a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=m;j>=1;j--)
            f4[i][j]=max(f4[i][j+1],f4[i-1][j])+a[i][j];
    res=0;
    for(int i=2;i<n;i++)
        for(int j=2;j<m;j++){
            res=max(res,f1[i-1][j]+f2[i+1][j]+f3[i][j-1]+f4[i][j+1]);
            res=max(res,f1[i][j-1]+f2[i][j+1]+f3[i+1][j]+f4[i-1][j]);
        }
    printf("%d\n",res);
    return 0;
}