比赛 国庆欢乐赛3 评测结果 AAAAAAAAAAAAAAA
题目名称 Following Directions 最终得分 100
用户昵称 李奇文 运行时间 0.991 s
代码语言 C++ 内存使用 13.18 MiB
提交时间 2025-10-05 10:19:06
显示代码纯文本
#include<bits/stdc++.h>

using namespace std;
const int N=1505;
int n,q,ans,op;
char a[N][N];
int d[N][N],c[N][N];
void dfs(int x,int y,int k){
    d[x][y]+=k;
    if(y==n+1||x==n+1){
        op=c[x][y];
        return;
    }
    if(a[x][y]=='R'){
        dfs(x,y+1,k);
    }else{
        dfs(x+1,y,k);
    }
}
int main(){
    freopen("zunxun.in","r",stdin);
    freopen("zunxun.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            d[i][j]=1;
        }cin>>c[i][n+1];
    }
    for(int i=1;i<=n;i++) cin>>c[n+1][i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]=='R'){
                d[i][j+1]+=d[i][j]; 
            }else{
                d[i+1][j]+=d[i][j];
            }
        }
        ans+=d[i][n+1]*c[i][n+1];
    }
    for(int i=1;i<=n;i++){
        ans+=d[n+1][i]*c[n+1][i];
    }
    cout<<ans<<"\n";
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        int gg=d[x][y];
        dfs(x,y,-d[x][y]);
        ans-=op*gg;
        if(a[x][y]=='R') a[x][y]='D';
        else a[x][y]='R';
        op=0;
        dfs(x,y,gg);
        ans+=op*gg;
        cout<<ans<<"\n";
        op=0;
    }
    return 0;
}