题目理解

这是 BalticOI 2015 Bowling 问题的解决方案。题目要求计算与给定记录相符的不同比赛数目，考虑字符污损和分数污损的情况。

代码思路解析

1. 状态定义

使用四维DP数组：

f[i][j][k][o]

• i: 当前局数（1 ≤ i ≤ n）
• j: 累计得分
• k: 前一局第一次投掷的击倒数（11表示未知）
• o: 前一局第二次投掷的击倒数（11表示未知）

2. 状态转移

代码根据不同的字符组合情况进行状态转移：

情况1：全中（strike）

if (u == 'x' || v == '-') {
    // 全中情况，得分 = 10 + 下两次投掷
    f[i][j + 10 + k + o][k][o] += ...
}

情况2：补中（spare）

if (u >= '0' && u <= '9' && v == '/') {
    // 补中情况，得分 = 10 + 下一次投掷
    f[i][j + 10 + k][k][11] += ...
}

情况3：普通局

if (u >= '0' && u <= '9' && v >= '0' && v <= '9') {
    // 普通情况，得分 = A + B
    f[i][j + u - '0' + v - '0'][11][11] += ...
}

3. 最终局特殊处理

最终局有3次投掷机会，需要单独处理所有可能的组合：

• xxx、xxA、xA/、xAB、A/x、A/B、AB-

for (int x = 0; x <= 10; ++ x) {      // 第一次投掷
    for (int y = 0; y <= 10; ++ y) {  // 第二次投掷  
        for (int z = 0; z <= 10; ++ z) { // 第三次投掷
            // 检查是否符合最终局规则
            // 累加合法方案数
        }
    }
}

关键技巧

1. 未知状态表示

使用 11 表示未知的击倒数，这样可以统一处理污损字符。

2. 分数验证

if (a[i] == -1 || j + score == a[i])

只有当分数未被污损时，才验证累计得分是否匹配。

3. 规则约束

在状态转移时严格检查保龄球规则：

• 全中后局结束
• 补中需要两次投掷击倒10瓶
• 普通局两次投掷和小于10

复杂度分析

• 状态数：n × 30n × 12 × 12 ≈ 4320n²
• 对于 n ≤ 10，状态数约 432,000
• 最终局三重循环：11 × 11 × 11 = 1331
• 总复杂度：可接受

总结

这个解法是典型的动态规划计数问题，通过：

1. 定义合适的状态表示
2. 根据规则分类讨论状态转移
3. 处理污损字符和分数的特殊情况
4. 最终局单独处理复杂规则

代码虽然较长，但逻辑清晰，完整地模拟了保龄球比赛的所有可能情况。