题解：AT_arc197_a 网格路径并

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_{re} = (H - 1) - totd

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

定义 pre[i] 为字符串前

i

个字符中 ? 的个数，考虑前

i

步中选取

x

个 ? 变为 ?，则要求

\max\Bigl(0,\; d_{re} - (totf - pre_i)\Bigr) \le x \le \min(pre_i,\; d_{re}).

对于第

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).

CPP

#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;
}

题解：AT_arc197_a 网格路径并

文章操作

AT_arc197_a 网格路径并

题目大意

解题思路

相关推荐

评论

题解：AT_arc197_a 网格路径并