Following Directions

题目描述

注意：本题时间限制为 8s，是默认时间限制的 4 倍。 农夫约翰有一块巨大的正方形田地，被划分为一个 $(N+1) imes (N+1)$ 的网格（$1\le N\le 1500$）。用 $(i, j)$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子。对于所有满足 $1 \le i, j \le N$ 的格子 $(i, j)$，每个格子里住着一头奶牛，并且该格子里还有一个路标，指向右方或下方。

此外，所有满足 $i=N+1$ 或 $j=N+1$ 的格子（除了 $(N+1, N+1)$ 之外）都放着一桶牛饲料。每桶饲料的价格不同：位于 $(i, j)$ 的饲料桶对每头奶牛收费为 $c_{i, j}$（$1 \le c_{i,j} \le 500$）。

每天晚餐时间，农夫约翰会敲响晚餐铃声，每头奶牛会不断沿着路标指示的方向前进，直到到达某个饲料桶，然后从该桶进食。之后，所有奶牛都会回到各自原来的位置，等待第二天。

为了控制预算，农夫约翰想知道每天喂所有奶牛的总成本。然而，每天晚餐前，会有某个格子 $(i, j)$ 中的奶牛把该格子的路标方向翻转一次（从右变下或从下变右）。路标会保持翻转后的方向，直到之后某天再次被翻回。

给定每天被翻转的路标坐标，请输出每天的总成本（共 $Q$ 天，$1 \le Q \le 1500$）。

输入格式

第一行包含 $N$（$1 \le N \le 1500$）。 接下来 $N+1$ 行按从上到下给出网格每一行的信息，包含路标的初始方向以及每个饲料桶的费用 $c_{i, j}$。 其中前 $N$ 行：每行先给出一个长度为 $N$ 的字符串，由字符 R 或 D 组成（分别表示路标指向右或下），然后给出费用 $c_{i, N+1}$。 第 $(N+1)$ 行包含 $N$ 个费用 $c_{N+1, j}$。 下一行包含 $Q$（$1 \le Q \le 1500$）。 接下来有 $Q$ 行，每行包含两个整数 $i$ 和 $j$（$1 \le i, j \le N$），表示对应那一天被翻转路标的格子坐标。

输出格式

输出共 $Q+1$ 行：第一行输出初始状态下的总成本，之后依次输出每次翻转之后的总成本。

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

602
701
602
701
1501

提示

在第一次翻转之前，位于 $(1, 1)$ 与 $(1, 2)$ 的奶牛喂养成本为 $1$，位于 $(2, 1)$ 的奶牛喂养成本为 $100$，位于 $(2, 2)$ 的奶牛喂养成本为 $500$，总成本为 $602$。第一次翻转后，$(1,1)$ 的路标方向从 R 变为 D，因此 $(1, 1)$ 的奶牛现在喂养成本为 $100$（其余不变），总成本变为 $701$。第二次与第三次翻转将同一个路标来回切换。第四次翻转后，位于 $(1, 1)$ 与 $(2, 1)$ 的奶牛喂养成本都变为 $500$，因此总成本为 $1501$。 SCORING: Inputs 2-4: $1 \le N, Q \le 50$ Inputs 5-7: $1 \le N, Q \le 250$ Inputs 2-10: 每个格子的初始方向以及查询均为均匀随机生成。 Inputs 11-15: 无额外限制。 题目来源：Benjamin Qi

标签: USACO|2023|Silver

来源

USACO|2023|Silver