题解：P14710 [ICPC 2023 Tehran R] Star Wars

WE_TRT · 2025-12-12 10:00:43 · 题解

一道简单的DP题。

思路：

题目给出了棋子可以往正上方、左上方、右上方行走。咱们反过来看，每个点位（除了白棋子）都可以从正上方、左上方、右上方走过来，所以到这个点可以击落的黑棋子数量就是能到达这个点位且不是白棋子的点位（因为白棋子根本走不到）中的最大值，如果这个点位是黑棋子，那么需要再加一。剩余解析看注释。

代码：

#include<bits/stdc++.h>
using namespace std;
const int Nmax=55;
int n,m,dp[Nmax][Nmax];
char a[Nmax][Nmax];
int ans=-2e9;
int main(){
    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++){
            if(a[i-1][j]!='W'){
                dp[i][j]=dp[i-1][j];
            }
            if(j>1&&a[i-1][j-1]!='W'){//特判不要越界且不是白棋子。
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
            }
            if(j<m&&a[i-1][j+1]!='W'){//也是特判不要越界且不是白棋子。
                dp[i][j]=max(dp[i][j],dp[i-1][j+1]);
            }
            if(a[i][j]=='B'){//如果是黑棋子，就再加一。
                dp[i][j]+=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='W'){
                ans=max(ans,dp[i][j]);//取从所有白棋子开始能击落多少个黑棋子的最大值。
            }
        }
    }
    cout<<ans;
    return 0;
}