A2138. Facer爱游泳
编程题
提高+/省选-
知识点
题目描述
Facer 是一个爱游泳的孩子。一天他来到了一个 $n \times m$ 的游泳池中，其中第一行是水面，第 $n$ 行是游泳池底。
Facer 想要从 $(1,1)$ 游到 $(1,m)$。他初始速度为 $0$ m/s。
Facer 可以按照以下方式游泳：假设当前 Facer 位于 $(x,y)$，速度为 $v$，那么它可以游到 $(x+v,y+1)$，如果 $x+v>n$，那么就会游到 $(n,y+1)$。
到了每一个格子，Facer 可以选择将自己的速度 $+1$，$-1$ 或者不变，也就是说每次 Facer 有三种选择：
- 游到 $(x+v-1,y+1)$，速度变为 $v-1$。
- 游到 $(x+v,y+1)$，速度变为 $v$。
- 游到 $(x+v+1,y+1)$，速度变为 $v+1$。
游泳池的每个格子上会放有以下两种物品中的一种：
- 变速器，每个变速器有一个属性 $w$，到了这个格子速度会变为 $v+w$（当然原来的 $+1$，$-1$，不变照样存在）。
- 金币盒，每个金币盒中有一定数量的钱 $a$，到了这个位置你可以得到 $a$ 个金币。
除此之外，有以下两点需要注意的：
1. 当 Facer 到达水面，即位于 $(1,x)$ 时，Facer的速度会变成 $0$（当然他仍然可以选择将速度 $+1$，$-1$ 或不变）。
2. Facer 不能在水下待太长时间，相邻两次到水面换气的时间不能超过 $k$ 秒。
求 Facer 能够得到最大金币的数量。
Facer 想要从 $(1,1)$ 游到 $(1,m)$。他初始速度为 $0$ m/s。
Facer 可以按照以下方式游泳：假设当前 Facer 位于 $(x,y)$，速度为 $v$，那么它可以游到 $(x+v,y+1)$，如果 $x+v>n$，那么就会游到 $(n,y+1)$。
到了每一个格子，Facer 可以选择将自己的速度 $+1$，$-1$ 或者不变，也就是说每次 Facer 有三种选择：
- 游到 $(x+v-1,y+1)$，速度变为 $v-1$。
- 游到 $(x+v,y+1)$，速度变为 $v$。
- 游到 $(x+v+1,y+1)$，速度变为 $v+1$。
游泳池的每个格子上会放有以下两种物品中的一种：
- 变速器，每个变速器有一个属性 $w$，到了这个格子速度会变为 $v+w$（当然原来的 $+1$，$-1$，不变照样存在）。
- 金币盒，每个金币盒中有一定数量的钱 $a$，到了这个位置你可以得到 $a$ 个金币。
除此之外，有以下两点需要注意的：
1. 当 Facer 到达水面，即位于 $(1,x)$ 时，Facer的速度会变成 $0$（当然他仍然可以选择将速度 $+1$，$-1$ 或不变）。
2. Facer 不能在水下待太长时间，相邻两次到水面换气的时间不能超过 $k$ 秒。
求 Facer 能够得到最大金币的数量。
输入格式
第一行三个整数 $n,m,k$。
第二行到第 $n+1$ 行，每行 $m$ 个字符串，表示每个格子物品的情况：
- 首字母为 ``
- 首字母为 ``
第二行到第 $n+1$ 行，每行 $m$ 个字符串，表示每个格子物品的情况：
- 首字母为 ``
v``，后面接一个整数 $w$，表示该格子中有一个变速器，属性为 $w$。- 首字母为 ``
s``，后面接一个整数 $a$，表示该格子中有一个金币盒，钱数为 $a$。输出格式
一行一个整数表示答案。
输入输出样例
输入 #1
3 3 3 s1 v1 s1 s3 s19 v2 v3 s-1 v-1
输出 #1
2
输入 #2
5 10 3 s81 s47 s3 s0 s82 s31 s89 v0 s97 v-1 s14 s94 v1 v-1 v1 s106 v1 v0 v-1 v0 s93 s105 v-1 s219 v0 v0 v-1 v1 s225 v1 v0 s160 v1 v1 s348 s120 s240 s392 s280 s172 s305 s455 s140 v-1 s455 v0 v-1 v0 v1 s410
输出 #2
430
说明/提示
$1 \leq n \leq 100$，$1 \leq m \leq 1000$，$1 \leq k \leq 10$，$-20 \leq w \leq 20$，$-1000 \leq a \leq 1000$。