比赛场次 574
比赛名称 4043级2023省选模拟赛6
比赛状态 已结束比赛成绩
开始时间 2023-03-28 08:00:00
结束时间 2023-03-28 12:00:00
开放分组 全部用户
注释介绍 好题,深入交流
题目名称 Following Directions
输入输出 zunxun.in/out
时间限制 2000 ms (2 s)
内存限制 256 MiB
测试点数 15 简单对比
用户 结果 时间 内存 得分
Gravatarop_组撒头屯 AAAAAAAAAAAAAAA 0.866 s 13.44 MiB 100
Gravataryrtiop AAAAAAAAAAAAAAA 1.297 s 18.24 MiB 100
Gravatarムラサメ AAAAAAAAAAAAAAA 1.333 s 13.98 MiB 100

Following Directions

★★☆   输入文件:zunxun.in   输出文件:zunxun.out   简单对比
时间限制:2 s   内存限制:256 MiB

【题目描述】

约翰的农场可以看作一个 $(N+1)×(N+1)$ 的方格矩阵。

矩阵行从上到下编号 $1 \sim N+1$,列从左到右编号 $1 \sim N+1$。

第 $i$ 行第 $j$ 列的方格表示为 $(i,j)$。

满足 $1≤i,j≤N$ 的每个方格 $(i,j)$中都居住着一头奶牛,并且每个这样的方格中都有一个向右或向下的路标。

此外,除了 方格$(N+1,N+1)$ 之外,满足 $i=N+1$ 或 $j=N+1$ 的每个方格 $(i,j)$ 中都有一桶牛饲料,饲料成本为 $c_{i,j}$。

也就是说,每当有一头奶牛来到方格 $(i,j)$ 处吃牛饲料,约翰就需要付出 $c_i$ 的成本。


每头奶牛每天只吃一顿饭,用餐时间在晚上。

每天晚餐时间,约翰都会敲响晚餐铃,奶牛们就会遵循路标指示不断前进,直到到达有牛饲料的方格,奶牛就会停下来进食。

所有奶牛在吃完饲料后,都会回到自己的住所休息。

为了维持预算,约翰想知道每天喂养所有奶牛的总成本。

然而,每天开始晚餐前,都会有一个单元格 $(i,j)$ 中的奶牛翻转其所在方格的路标方向(向右变向下,向下变向右)。


注意,每一天的路标翻转都会对后续天产生影响。


路标方向一旦改变,在接下来的日子里,除非在某一天它又被奶牛翻转回来,否则,它不会自己翻转回来。

一共有 $Q$ 天时间,给定每天翻转路标的单元格坐标,请你计算初始总成本以及每天的实际总成本。

【输入格式】

第一行包含整数 $N$。

接下来 $N+1$ 行,包含路标的初始方向和每桶饲料的成本:

   前 $N$ 行:第 $i$ 行包含一个长度为 $N$ 的由 $R$ 和 $D$ 组成字符串,其中的第 $j$ 个字符表示方格 $(i,j)$ 的路标方向($R$ 表示向右,$D$ 表示向下),紧接着是一个整数 $C_{i,N+1}$ 表示方格 $(i,N+1)$ 的饲料成本。

   第 $N+1$ 行:包含 $N$ 个整数 $C_{N+1,1},C_{N+1,2},…,C_{N+1,N}$ ,表示方格 $(N+1,j)$ 的饲料成本。


接下来一行包含整数 $Q$。

接下来 $Q$ 行,其中第 $i$ 行包含两个整数 $a_i,b_i$,表示第 $i$ 天晚饭前翻转路标的单元格坐标为 $(a_i,b_i)$。

【输出格式】

共 $Q+1$ 行。

第一行输出初始总成本,即没有任何翻转的情况下每天的晚餐总成本。

接下来 $Q$ 行,其中第 $i$ 行输出第 $i$ 天的实际晚餐总成本。

【样例1输入】

2
RR 1
DD 10
100 500
4
1 1
1 1
1 1
2 1

【样例1输出】

602
701
602
701
1501

【样例2】

点击下载样例2

【样例1说明】

初始时,方格 $(1,1)$ 和 $(1,2)$ 的奶牛饲养成本均为 $1$,方格 $(2,1)$ 的奶牛饲养成本为 $100$,方格 $(2,2)$ 的奶牛饲养成本为 $500$,总成本为 $602$。

第一次翻转后,方格 $(1,1)$ 处的路标方向从 $R$ 变为 $D$,此时方格 $(1,1)$ 处的奶牛饲养成本变为 $100$,其余保持不变,所以总成本变为 $701$。

第二次翻转后,矩阵变回初始状态,总成本为 $602$。

第三次翻转后,矩阵变为第一次翻转后状态,总成本为 $701$。

第四次翻转后,方格 $(1,1)$ 和 $(2,1)$ 的奶牛饲养成本均变为 $500$,总成本为 $1501$。

【数据规模与约定】

测试点 $2-4:1≤N,Q≤50$;

测试点 $5-7:1≤N,Q≤250$;

测试点 $2-10$:每个单元格中的初始方向以及查询都是随机生成的。

对于 $100\%$ 的数据,$1≤N≤1500,1≤c_i,j≤500,1≤Q≤1500,1≤a_i,b_i≤N$。