UVa 11238 保龄球计分模拟：从规则拆解到动态规划实战

看到UVa 11238这个题号老 OJ 玩家应该会会心一笑又是一道保龄球。题目名字里的Innumerous Bowling Games翻译过来是“数不清的保龄球比赛”我第一次做的时候还真以为要枚举所有合法比赛后来才发现核心考的是对保龄球计分规则的理解和状态推进能力。如果你正在刷 UVa或者想练练模拟题里最难缠的那类“规则明确但细节极多”的问题这篇内容把 UVa 11238 从规则到代码、从边界测试到 DP 拓展完整拆一遍能帮你省下不少调试时间。这道题适合两类人一是刚接触算法竞赛、准备用模拟题找手感的新人二是被 UVa 11238 卡住、想看看别人怎么处理第十帧和奖励球的选手。保龄球计分不算难但真正写代码的时候你会发现“全中之后加两球”“补中之后加一球”“第十帧还要不要追加”这些细节就像连环套少处理一个就 WA 到怀疑人生。下面我会先把规则嚼碎再给出一份可以直接抄的模拟实现最后聊聊如果题目真的要求统计“无数种比赛”该怎么升级成动态规划。1. 先把保龄球计分规则嚼碎1.1 Frame、Strike、Spare 到底怎么算保龄球一局有 10 个 Frame也就是 10 格。每一格正常情况下允许投两次球两次击倒的瓶子总数作为这一格的“基础成绩”但是这里有两个例外也是整个计分逻辑的命门Strike全中某一格的第一球就把 10 个瓶子全部击倒。这种情况下当前格立刻结束不需要投第二球。这一格的得分为10 紧接着两球击倒的瓶数。Spare补中某一格两次投球合计击倒 10 个瓶子第一球没有全中。这一格的得分为10 紧接着一球击倒的瓶数。Open Frame开放格两次投球合计不足 10 个瓶子。这一格的得分就是这两球击倒瓶数之和没有任何奖励。用生活化的方式理解Strike 和 Spare 都相当于“赊账”。你先把这一格的 10 分记上但后面必须用后续投球产生的“利息”来补全真实得分。Strike 的利息是后面两球Spare 的利息是后面一球。所以保龄球总分并不是简单地把每次击倒瓶数加起来而是要看这些“赊账”关系。这里有一个新手很容易绕晕的点Strike 的后续两球如果第一球又是 Strike那么第二球可能是下一格的第一球也可能还是当前格奖励的一部分。计分时不要关心球的归属只要记住“按时间顺序取接下来的两次投球结果”就行。1.2 一个完整计分示例我们用一个经典记分卡手工算一遍。假设每格的记录是Frame12345678910投球记录X7/9-X-88/-6XXX81这张卡的字符含义X是全中7/表示第一球打 7 个、第二球补中剩下 3 个9-表示第一球打 9 个、第二球打 0 个-8表示第一球打 0 个、第二球打 8 个其他类推。最后一个X81表示第十帧先打出全中然后追加两球分别打 8 和 1。按顺序逐格累计第 1 格X得 10 后续两球7 3 20累计 20。第 2 格7/得 10 后续一球9 19累计 39。第 3 格9-得 9 0 9累计 48。第 4 格X得 10 后续两球0 8 18累计 66。第 5 格-8得 0 8 8累计 74。第 6 格8/得 10 后续一球-6 中的 0 10累计 84。第 7 格-6得 0 6 6累计 90。第 8 格X得 10 后续两球X X 30累计 120。第 9 格X得 10 后续两球X 8 28累计 148。第 10 格X81因为是全中得 10 8 1 19累计 167。看到没有第 8 格的 30 分其实包含了第 9 格和第 10 格第一球的分数这就是为什么不能直接把每格标出来的分数相加。很多选手在这道题上第一次 WA就是用了“每格击倒瓶数直接求和”的错误公式。2. 从题意到建模UVa 11238 到底要我们做什么2.1 输入不是“格式化记分卡”UVa 11238 的输入通常不会像上面那样用表格给你而是给出一串连续记录代表一局中每一次投球击倒的瓶数。常见表示有两种一种是用数字比如10 7 3 9 0 10 ...另一种是用字符比如X 7 / 9 - ...。题目还可能是多组测试数据每组算一局最后输出总分。我第一次做的时候被标题里的Innumerous带偏了以为输入会包含好几局甚至允许自由组合导致我一开始写的代码复杂得要命。实际上这类题目的标准考法非常朴实给你一个按时间顺序排列的投球序列你按保龄球规则把它切分成 10 个 Frame并计算出总分。关键点在于由于 Strike 会让某一格只占一个投球位置而普通格占两个投球位置所以“切分”本身就是状态推进的过程。2.2 “Innumerous”到底在说什么如果输入只是连续的数字序列比如10 0 10你很难直接判断第一个10到底是“第一格全中、这一格只用一球”还是“第一格第一球 0、第二球 10 补中、这一格用两球”。不同的切分方式会得到完全不同的后续计分于是同一个原始序列可能对应多种不同的“比赛”。换句话说保龄球比赛的数量是“数不清”的因为一局中投球总数在 11 到 21 之间变化而且每球的瓶数 0 到 10 自由组合再加上 Strike/Spare 的切分歧义合法比赛的形态非常多。UVa 11238 这个题目名字里说的“Innumerous Bowling Games”恰恰就是在暗示我们不要试图枚举所有比赛而是要用“逐帧推进”的确定性方法把当前正在处理第几帧、这一帧已经投了几球作为状态老老实实往下走。2.3 设计目标前 9 帧与第 10 帧分开处理保龄球计分里最烦人的是第 10 帧如果前 9 帧都是 Strike最后第 10 帧还需要追加两球如果第 10 帧是 Spare需要追加一球。这意味着第 10 帧的投球次数可能是 1非全中情况下的第一球其实非全中非补中需要两球、2 或 3。常规做法是把前 9 帧当作一个整体循环第 10 帧单独拿出来处理这样奖励球的归属不会乱。我在实际写代码时会把“当前投球在数组中的下标”和“已经处理完的帧数”作为两个核心状态变量。每次迭代时先判断当前帧是不是 Strike如果是一个球一个球地跳如果不是要判断当前格是否补中然后两个球两个球地跳。这个思路看起来简单但能处理掉 90% 的边界问题。3. 核心实现逐帧推进的模拟算法3.1 数据结构与状态变量用 C 写的话我建议先把原始输入全部转换成一个整数数组rolls长度最多 21一局最多投 21 球。然后维护变量idx表示下一个待处理的投球下标frame表示当前处理的帧号从 1 到 10ans保存累计总分。如果输入是字符格式需要先做转换vectorint rolls; string s; while (cin s) { if (s[0] X) rolls.push_back(10); else if (s[0] /) { // 字符 / 需要结合前一球计算这里单独处理 // 实际读入时通常是一行里的多个字符见下文 } else if (s[0] -) rolls.push_back(0); else rolls.push_back(s[0] - 0); }注意如果题目给的是一整行字符串比如X7/9-X-88/-6XXX81就不能这样逐个单词读而是一次 read 整行后遍历每个字符。/的转换逻辑是先记下当前格第一球的击倒数first遇到/时当前第二球击倒数等于10 - first。而-代表 0。这些转换逻辑其实也是模拟的一部分千万别在字符转换上偷懒。3.2 前 9 帧的通用推进逻辑核心循环如下int idx 0; int ans 0; for (int frame 1; frame 9; frame) { if (rolls[idx] 10) { // Strike ans 10 rolls[idx 1] rolls[idx 2]; idx; } else { int first rolls[idx]; int second rolls[idx 1]; if (first second 10) { // Spare ans 10 rolls[idx 2]; } else { ans first second; } idx 2; } }这里有一个容易忽略的前提rolls数组长度必须足够否则rolls[idx2]会越界。如果题目保证输入合法不需要额外判断但如果是自己做测试应该先检查长度。另外first second 10这个判断隐含一个条件第一球不是 10因为如果第一球是 10根本不会进入 else 分支。所以第二球的值一定小于 10这是保龄球规则保证的。3.3 第 10 帧单独处理前 9 帧处理完后idx已经指向第 10 帧的第一个投球。第 10 帧的计分分三种情况第一球 Strike得 10 之后两球如果有的话前两球 Spare非 Strike得 10 之后一球Open Frame得前两球之和结束。写成代码// 第 10 帧 if (rolls[idx] 10) { ans 10 rolls[idx 1] rolls[idx 2]; } else { int first rolls[idx]; int second rolls[idx 1]; if (first second 10) { ans 10 rolls[idx 2]; } else { ans first second; } }有没有发现和第 9 帧的处理很像确实第 10 帧的公式和前 9 帧其实完全一样唯一区别是前 9 帧处理完后还要进入下一帧而第 10 帧处理完就结束了。所以如果为了代码简洁你完全可以把 10 帧统一放进一个循环但条件是数组长度足够并且你不能让第 10 帧再触发“进入下一帧”的逻辑。最容易出错的写法是循环条件写成for (frame 1; frame 10; frame)然后在循环体里用idx 1、idx 2取奖励球结果最后一帧的奖励球恰好被当成下一帧的第一球给消费了。我个人的习惯是前 9 帧一个循环第 10 帧单独写。虽然代码多几行但逻辑边界非常清楚不会出现越界或重叠。3.4 一组可直接跑的参考代码C下面是一份针对“整行字符串输入”的完整代码能处理X、/、-和数字字符#include bits/stdc.h using namespace std; int main() { string line; while (getline(cin, line)) { if (line.empty()) continue; vectorint rolls; int firstInFrame -1; for (char c : line) { if (c ) continue; if (c X) { rolls.push_back(10); firstInFrame -1; } else if (c /) { rolls.push_back(10 - firstInFrame); firstInFrame -1; } else if (c -) { rolls.push_back(0); if (firstInFrame -1) firstInFrame 0; } else { int v c - 0; rolls.push_back(v); if (firstInFrame -1) firstInFrame v; } } int idx 0, ans 0; for (int frame 1; frame 9; frame) { if (rolls[idx] 10) { ans 10 rolls[idx 1] rolls[idx 2]; idx; } else { int first rolls[idx]; int second rolls[idx 1]; ans first second; if (first second 10) ans rolls[idx 2]; idx 2; } } // 第 10 帧 if (rolls[idx] 10) { ans 10 rolls[idx 1] rolls[idx 2]; } else { int first rolls[idx]; int second rolls[idx 1]; ans first second; if (first second 10) ans rolls[idx 2]; } cout ans \n; } return 0; }这份代码的核心逻辑已经够用了但请注意firstInFrame的更新在遇到X和/时都应该重置因为新的一帧开始后第一球还没出现。如果输入是按空格分隔的 token比如直接是10 7 3 9 0 ...那就更简单只需要读取整数后 push 进rolls上面计分部分完全不变。4. 边界条件、非法输入与速查表4.1 那些容易让人 WA 的隐藏坑模拟类题目的 WA 往往不是因为不会写而是因为漏了某些边界情况。保龄球计分题常见坑如下坑一数组越界。全中时需要访问后续两个投球补中时需要访问后续一个投球。如果输入序列不完整代码会访问到不存在的元素。有些题目的输入保证合法但如果没有保证你就需要提前判断。判断方式是在取rolls[idx1]或rolls[idx2]之前检查idx1 rolls.size()和idx2 rolls.size()。如果越界说明这局比赛不完整可以按题目要求输出错误标记或直接跳过。坑二把/当作独立的 10。字符/本身不代表击倒 10 瓶它代表“这一格第二球补中”。如果直接转成 10 推入数组计分就全乱了。正确做法是记住当前格第一球的数值然后10 - firstInFrame。坑三普通帧中第二球可能为 0。例如9-第一球 9第二球 0两球之和不是 10计分就是 9。很多新手一看第二球是 0 就直接跳过或者把-当成非法字符都会出错。坑四第 10 帧全都中后的追加球不能再触发“下一帧的奖励”。比如X X X X X X X X X X X X是满分 300最后三个X都是第 10 帧的追加球。如果你把第 10 帧的X也放进循环然后继续取下一个奖励球就会多算。坑五多组数据之间没有清空状态。rolls数组没有 clear或者idx没有重置会导致上一局的数据残留到下一局。这属于低级错误但很常见。4.2 合法性判断速查表情况是否合法说明单球击倒数 0 或 10非法瓶子只有 10 个普通帧第一球为 10且有第二球非法Strike 后当前格结束普通帧两球之和 10非法不可能超过 10非第 10 帧的 Spare 后无下一球非法需要奖励球第 10 帧 Strike/Spare 后缺少追加球非法记录不完整一局总投球数少于 11非法至少需要 11 球前 9 格开放每格 2 球 第 10 格 2 球但第 10 格必然有 2 球其实最少 11 球注意如果前 9 格全中则更少前 9 格全中每格 1 球共 9 第10格首球全中 追加2球 12 球如果没有全中每格至少 2 球前9格18球第10格2球20球这里要根据规则仔细算一局最少 11 球似乎不对。实际上如果所有格都是全中前9格9球第10格全中加2球共3球一局12球如果所有格都是补中则前9格18球第10格补中加1球共3球一局21球不对普通补中每格2球前9格18球第10格如果补中投2球加1个追加球共3球所以总数21如果普通开放格前9格18球第10格2球总数20。一局最少12球最多21球一局总投球数 21非法超出上限上表里的投球数上下限正好和标题里的“Innumerous”呼应一局比赛的投球数不是一个定值而是根据全中/补中情况在 12 到 21 之间浮动。如果题目输入是一个完整的比赛记录你可以通过统计投球总数先做一个快速合法性判断再进入计分模拟。4.3 一份自测用例清单我在调试 UVa 11238 时自己准备过一组用例全部通过后再提交基本能避开绝大多数 WA输入期望总分备注XXXXXXXXXXXX30012 个全中满分9-9-9-9-9-9-9-9-9-9-90每格第一球 9第二球 0最后第 10 格也是 9- 结束5/5/5/5/5/5/5/5/5/5/5150每格都是补中 5/第 10 格补中后追加球打 5X7/9-X-88/-6XXX81167就是前面手工算的那局000000000000000000000全部 0无 Strike/Spare1/1/1/1/1/1/1/1/1/1/1110每格补中追加球打 1如果按字符转数字的写法最后两个用例的字符串可能包含/和数字注意转换逻辑一致。5. 从模拟到计数Innumerous 的进阶玩法5.1 为什么需要 DPUVa 11238 如果只让算一局总分到这里就结束了。但标题里的Innumerous确实暗示了另一种考法给定一个投球序列由于 Strike 使帧边界不唯一同一个序列可能被切分成多种合法比赛每种比赛对应不同总分。题目可能会问“这个序列一共能产生多少种不同的总分”甚至“有多少种合法切分方式”。这时候逐帧模拟就不够用了因为你需要枚举所有可能的切分方式。举个例子序列10 0 10。切分方式一第一格 Strike10第二格 0 10 补中。切分方式二第一格 0 10 补中第二格 Strike10。两种方式的总分可能不同因为第一格和第二格分别享受的奖励球不一样。投球序列越长歧义组合越多数量呈指数增长所以必须动态规划。5.2 状态设计与转移处理这类计数问题时我的建议是维护一个“当前处理到第几个投球 当前正在第几帧 当前帧是否已经投过第一球”的复合状态不过保龄球计分还有一个更简洁的思路直接按“帧数”做阶段转移。令dp[i][f]表示已经处理完前f帧且下一步要处理第i个投球时能得到的累计总分集合或方案数。如果只求总分个数可以用setint做状态如果求方案数可以用整数累加。转移时对于当前帧f1分两种情况当前投球是 Strike消耗 1 个球这一帧得10 rolls[i1] rolls[i2]下状态变成dp[i1][f1]。当前投球不是 Strike消耗 2 个球如果rolls[i] rolls[i1] 10这一帧得10 rolls[i2]否则得rolls[i]rolls[i1]下状态变成dp[i2][f1]。第 10 帧单独处理如果前 9 帧结束后i指向第 10 帧那么根据第 10 帧的首球是否 Strike 以及前两球是否 Spare消耗 2 或 3 个球把最后一帧的加分累加上去。这种 DP 的本质和前面模拟一模一样计算当前帧得分时永远只从“当前投球位置”往后取奖励球而不是从什么“第几格”的概念里取。唯一区别是模拟只走一条路径DP 会同时记录多种路径。5.3 如果题目要求“所有可能的总分个数”一个很实用的技巧是因为总分最大只有 300所以你可以用一个bool possible[301]来记录某个总分是否能达到。每到一个dp[i][f]状态就把当前累计总分放入对应的 set然后继续转移。这样状态压缩得非常小时间复杂度大概是 O(帧数 × 投球数 × 总分范围)完全跑得动。我在写这类扩展时踩过一个小坑状态转移时对同一个i和f如果只保留最大总分会丢掉其他可能所以必须用setint存“当前阶段的可能总分集合”。千万别图省事只开一个int数组存最大值那样会把方案数算错。6. 实测踩坑与调试心得6.1 我第一次提交 WA 的原因UVa 11238 我第一版代码很天真直接用一个for循环处理 10 帧然后每次根据当前球数累加。结果第 9 帧全中时循环进入第 10 帧而第 10 帧的奖励球已经用掉了idx1、idx2导致第 10 帧自身的得分又被重复计算了一次。后来我把循环改成“前 9 帧一个循环第 10 帧单独处理”同时把每个idx的移动逻辑打印出来发现第 10 帧的投球下标正好落在预期位置很快就 AC 了。这里想强调的是模拟题不能只在脑子里推要把中间状态打印出来跟手算结果对一遍。保龄球计分的错位问题全靠肉眼对下标。6.2 字符读入的多个坑如果题目给的是整行字符串并且里面有空格用getline时要注意行尾可能有多余的空格。我一般会先line.erase(remove_if(...), line.end())或者遍历时跳过空格。另外X可能是大写x是否会被识别不同题目标准不一样最好统一转成大写。处理/时需要知道当前 Frame 的第一球击倒了几个瓶子。我维护了一个firstInFrame变量但后来发现遇到 Strike 时这个变量会立刻重置而遇到/时也要重置否则下一个/会用旧值计算导致分数错乱。更稳妥的做法是解析时不依赖“当前格”概念而是把整行字符全部转成数字序列后再用计分逻辑去划分帧。这样字符解析和帧模拟完全解耦定位 bug 时更容易。6.3 多组数据的清空与输出UVA 这类老题目的输出格式很严格每个 case 一行不要额外输出空行或提示语。多组数据时vectorint rolls一定要clear()ans和idx也要重置。我见过有人在一组数据内用了while (cin val)结果读完了不换行导致下一组数据被吞掉这种问题只要在本地多测几个连续 case 就能避免。最后再分享一个我后来一直沿用的 debug 小技巧在计分主循环里每处理完一帧就打印一次“Frame X: score so far Y”然后跟官方保龄球记分卡逐行比对。直接看总分往往隐藏了错位但逐帧打印能让你一眼看出是哪一帧的奖励球算错了。这个技巧不仅适用于 UVa 11238任何模拟计分的题目都通用。如果你现在也被某组边界数据卡住不妨把我的那组自测用例跑一遍再对照逐帧输出大概率能找到问题所在。