题解：P12679 Brooklyn Round 1 & NNOI Round 1 C - Field

zzy_zzy · 2025-07-04 10:46:32 · 题解

鲜花

期末考完，作业全免，心情很好，故作此文。

题解

看到这种求矩阵路径最大的题，先考虑 dp。

但是对于这道题只设置一个状态显然是不够的，因为你无法使用一个状态来处理黑色格子“延迟加”这种东西，因此考虑设两个状态：

这样，转移就很简单了，遇到白格子的时候，分讨一下上一个格子的颜色；遇到黑格子的时候，记得比较的是 dp2 的大小。

不懂的参见代码：

#include<bits/stdc++.h>
using namespace std;
int a[1010][1010];
bool b[1010][1010];
int dp1[1010][1010];
int dp2[1010][1010];

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++)cin>>b[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(b[i][j]){
                if(b[i][j-1]){
                    dp1[i][j]=dp1[i][j-1]+a[i][j];
                    dp2[i][j]=dp2[i][j-1]+a[i][j];
                }
                else{
                    dp1[i][j]=dp1[i][j-1];
                    dp2[i][j]=dp2[i][j-1];
                }
                if(b[i-1][j]){
                    dp1[i][j]=max(dp1[i][j],dp1[i-1][j]+a[i][j]);
                    dp2[i][j]=max(dp2[i][j],dp2[i-1][j]+a[i][j]);
                }
                else{
                    dp1[i][j]=max(dp1[i][j],dp1[i-1][j]);
                    dp2[i][j]=max(dp2[i][j],dp2[i-1][j]);
                }
            }
            else{
                if(dp2[i][j-1]>dp2[i-1][j]){
                    dp1[i][j]=dp2[i][j-1];
                    dp2[i][j]=dp1[i][j]+a[i][j];
                }
                else{
                    dp1[i][j]=dp2[i-1][j];
                    dp2[i][j]=dp1[i][j]+a[i][j];
                }
            }
        }
    }
    cout<<dp1[n][m];
    return 0;
}