luogu#P1174. 打砖块
打砖块
题目描述
小红很喜欢玩一个叫打砖块的游戏,这个游戏的规则如下:
在刚开始的时候,有 行 列的砖块,小红有 发子弹。小红每次可以用一发子弹,打碎某一列当前处于这一列最下面的那块砖,并且得到相应的得分。(如图所示)
某些砖块在打碎以后,还可能将得到一发子弹的奖励。最后当所有的砖块都打碎了,或者小红没有子弹了,游戏结束。
小红在游戏开始之前,就已经知道每一块砖在打碎以后的得分,并且知道能不能得到一发奖励的子弹。小红想知道在这次游戏中她可能的最大得分,可是这个问题对于她来说太难了,你能帮帮她吗?
输入格式
第一行有 个正整数,。表示开始的时候,有 行 列的砖块,小红有 发子弹。
接下来有 行,每行的格式如下:
其中 为正整数,表示这一行的第 列的砖,在打碎以后的得分。 为一个字符,只有两种可能,Y
或者 N
。Y
表示有一发奖励的子弹,N
表示没有。
所有的数与字符之间用一个空格隔开,行末没有多余的空格。
输出格式
仅一个正整数,表示最大的得分。
3 4 2
9 N 5 N 1 N 8 N
5 N 5 Y 5 N 5 N
6 N 2 N 4 N 3 N
13
提示
对于 的数据,满足 ,,所有的字符 都为 N
。
对于 的数据,满足 ,,所有的字符 都为 N
。
对于 的数据,满足 ,,字符 可能为 Y
。
对于 的数据,所有的 值满足 。