题解：AT_arc197_a 网格路径并

SunburstFan · 2025-05-10 15:14:45 · 题解

AT_arc197_a 网格路径并

题目大意

给定一个 H \times W 的白色网格以及一个长度为 H+W-2 的字符串 S（字符为 D、R 和 ?），其中

• 若 S_i = \texttt{D}，第 i 步只能向下走；
• 若 S_i = \texttt{R}，第 i 步只能向右走；
• 若 S_i = \texttt{?}，第 i 步可以自由选择（向下或向右）。

每次你可以按照 S 允许的走法走一条从 (1,1) 到 (H,W) 的路径，并将路径上所有格子染成黑色。你可以多次操作，目标是使黑色格子总数尽可能多，求最大黑色格子的数量。

解题思路

一个合法路径必须走恰好 H-1 次“下”和 W-1 次“右”。

设字符串中固定的 D 数量为 totd，固定的字符总数为 totf 为 ? 的个数，则在每条合法路径中，还需要把 ? 中的

个字符选为 D（其余选为 R）。

定义 pre[i] 为字符串前 i 个字符中 ? 的个数，考虑前 i 步中选取 x 个 ? 变为 ?，则要求

对于第 i 前缀，合法的 x 数量即为 (u - l + 1),
其中 u = \min(pre_i,\; d_{re})
和 l = \max\Bigl(0,\; d_{re} - (totf - pre_i)\Bigr).

此时，固定的 D 数量加上从 ? 中选出的 x 个 D，确定了当前下走的总次数，从而唯一确定了路径在网格中的位置。
最终答案为所有前缀（i = 0 到 H+W-2）上合法取值数的总和。
由于对每个前缀只作常数次运算，整体时间复杂度为 O(H + W).

#include<bits/stdc++.h>
using namespace std;

void FileIO(){
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair

namespace sunburstfan{
    #define int long long
    const int mod=1e9+7;
    const int N=1e5+5;

    void solve(){
        int n,m;
        cin>>n>>m;
        string s;
        cin>>s;

        int len=n+m-2,totf=0,totd=0;
        for(int i=0;i<len;i++){
            if(s[i]=='?')totf++;
            else if(s[i]=='D')totd++;
        }

        int d_re=(n-1)-totd;
        //cout<<d_re<<" "<<totd<<"\n";

        int ans=0;
        vector<int> pre(len+1,0);
        for(int i=1;i<=len;i++){
            pre[i]=pre[i-1]+(s[i-1]=='?'? 1:0);
        }

        for(int i=0;i<=len;i++){
            int cur=pre[i];
            int l=max(0ll,d_re-(totf-cur)),u=min(cur,d_re);
            if(l<=u){
                ans+=(u-l+1);
            }
        }

        cout<<ans<<"\n";
    }
}
using namespace sunburstfan;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //FileIO();

    int T;
    cin>>T;

    while(T--){
        solve();
    }

    return 0;
}