P5157: 打砖块-训练套题T3T2
【题目描述】
1. game.pas/c/cpp) 【问题描述】 打砖块游戏规则如下： 刚开始时有n行m列的砖块，有k发子弹，每次可以用一发子弹，打碎处于某一列最下面的一块砖，并且得到相应的得分。 某些砖块在打碎后还可能得到一发子弹的奖励。最后当所有砖块都打碎了或者没有子弹了，游戏结束。 在游戏开始前，就知道每一块砖的得分、有没有奖励子弹。现在要知道最大得分。
【输入格式】 第一行有3个正整数，n，m，k 接下来有n行，每行的格式如下： f1 c1 f2 c2 f3 c3...fm cm 其中fi为正整数，表示这一行的第i列的砖块的得分，ci为一个字符，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 【问题规模】 对于20%的数据，满足1<=n,m<=5,1<=k<=10,所有的字符c都为N 对于50%的数据，满足1<=n,m<=200,1<=k<=200,所有的字符c都为N 对于100%的数据，满足1<=n,m<=200,1<=k<=200,字符c可能为Y 对于100%的数据，所有的f值满足1<=f<=10000
【提示】
打砖块
【题目大意】
给定k发子弹，要求得到最大的得分。在打碎某些砖块后，可能有一发子弹的奖励。
【解法一】
不考虑奖励的子弹，那么本题为一道简单的动态规划：
设b[i][j]表示对着前i列的砖块打j发子弹，能达到的最大得分。
考虑对着第i列发多少发子弹，可以得到状态转移方程为：
b[i][j]=max(b[i-1][j-k]+s[i][k])， (0≤k，k≤ j，k≤n)
其中s[i][k]表示对着第i列打k．发子弹的得分。这个数组可以在O(nm)时间内预处理出来。
最终答案为b[m][k]。时间复杂度为Ol(mnk)。预计得分50。
【解法二】
解法一的缺陷在于没有考虑能否得到一发奖励的子弹。对于一个能打到的砖块，如果有奖励子弹，那么能打肯定打，因为打了以后，不仅有得分，而且子弹也没有减少。所以解法一中的b[i][j]的定义稍作修改，b[i][j]表示对着前i列的砖块打j发自己的子弹(不包括奖励的子弹)，能达到的最大得分。
考虑对着第i列发多少发子弹，同样可以得到状态转移方程为：
b[i][j]=ma x(b[i-1][j-k]+s[i][k] (0≤k，k≤j，k≤n)
其中s[i][k]表示对着第i列打k发子弹的得分，如果在这个过程中有奖励子弹，那么奖励的子弹也对着这一列打。
这又产生了一个新的问题，对着第i列的砖打了k发子弹后，可能这一列现在处于最
下方的砖是有奖励子弹的，那么这一块砖的得分算不算在s[i][k]呢?
这需要分情况讨论：够最后一发子弹打的那一列不能算，而其余的都要算上。因为对
于别的列，可以借这最后一发的子弹先打砖块，然后用奖励的子弹归还。所以b数组要改
变两个：by[i][j]表示对着前i列的砖块打j发自己的子弹，且最后一发子弹不是对着前i列发，能达到的最大得分；by[i][j]表示对着前i列的砖块打j发自己的子弹，且最后一发子弹对着前i列发，能达到的最大得分。
递推的时候要讨论当前对着第i列的子弹是不是最后发的。
时间复杂度仍为O(mnk)。预计得分100。
【出题人的意图】
本题是这次模拟赛的第2题。因为基本上每年的NO I P都有一道动态规划的题目，所
以决定本题考动态规划。开始时想到了没有奖励子弹的模型，后来想加大一点难度，所以
就改成了奖励一发子弹的情形。
解法二中，如果没有分情况考虑，那么会失去一部分的分数。如果认为一定算在内，那
么失50分，如果认为一定不算在内，那么失40分。