题目分析

JYY 参加了 $N$ 轮保龄球比赛，每轮有两次投球机会。根据击倒瓶数分为三种情况：

• 全中：第一次击倒10瓶，下一轮得分翻倍
• 补中：两次共击倒10瓶，下一轮第一次投球得分翻倍
• 失误：两次共击倒少于10瓶，无翻倍效果

第 $N$ 轮若为全中则有附加轮。可以重新排列轮次顺序（保持轮数不变）来最大化总分。

解题思路

核心思想

使用动态规划结合分类讨论：

1. 将轮次按类型分类：全中、补中、失误
2. 设计高维DP状态记录各类轮次使用情况和翻倍状态
3. 枚举特殊轮次位置，尝试不同排序策略

关键技术

• 状态设计：六维DP状态跟踪进度和翻倍效果
• 轮次分类：不同类型轮次采用不同处理策略
• 贪心排序：对失误轮次尝试不同排序方法

算法步骤

1. 读入数据并分类轮次
2. 处理附加轮情况
3. 对失误轮次排序并枚举特殊轮
4. 运行DP计算最大得分
5. 输出最优结果

完整代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 53;
int n, flag, i, j, _, ca, cb, cc, cd, ans, f[N][N][N][N][2][3];
struct P {
    int x, y, z;
} a[N], b[N], c[N], d, _c[N];
inline bool cmpx(const P &a, const P &b) {
    return a.x > b.x;
}
inline bool cmpz(const P &a, const P &b) {
    return a.z > b.z;
}
inline void up(int &a, int b) {
    a < b ? (a = b) : 0;
}
void solve() {
    int i, j, r, k, S, o, w, v, t, x, y, cana, cane;

    for (i = 0; i <= ca; i++)
        for (j = 0; j <= cb; j++)
            for (r = cb; r >= j; r--)
                for (k = 0; k <= cc; k++)
                    for (S = 0; S <= cd; S++)
                        for (o = 0; o < 3; o++)
                            f[i][j][r][k][S][o] = -1;

    f[0][0][cb][0][0][0] = 0;

    for (i = 0; i <= ca; i++)
        for (j = 0; j <= cb; j++)
            for (r = cb; r >= j; r--)
                for (k = 0; k <= cc; k++)
                    for (S = 0; S <= cd; S++)
                        for (o = 0; o < 3; o++) {
                            w = f[i][j][r][k][S][o];

                            if (w < 0)
                                continue;

                            cana = cane = 1;

                            if (i + j + cb - r + k + S + 1 == n - 1)
                                cana = flag, cane = flag ^ 1;

                            if (cana && i < ca) {
                                t = 10;

                                if (o)
                                    t <<= 1;

                                up(f[i + 1][j][r][k][S][1], w + t);
                            }

                            if (!cane)
                                continue;

                            if (j < r) {
                                x = b[j + 1].x, y = b[j + 1].y;
                                t = x + y;

                                if (o == 1)
                                    t = (x + y) << 1;

                                if (o == 2)
                                    t = (x << 1) + y;

                                up(f[i][j + 1][r][k][S][2], w + t);
                                x = b[r].x, y = b[r].y;
                                t = x + y;

                                if (o == 1)
                                    t = (x + y) << 1;

                                if (o == 2)
                                    t = (x << 1) + y;

                                up(f[i][j][r - 1][k][S][2], w + t);
                            }

                            if (k < cc) {
                                x = c[k + 1].x, y = c[k + 1].y;
                                t = x + y;

                                if (o == 1)
                                    t = (x + y) << 1;

                                if (o == 2)
                                    t = (x << 1) + y;

                                up(f[i][j][r][k + 1][S][0], w + t);
                            }

                            if (S < cd) {
                                x = d.x, y = d.y;
                                t = x + y;

                                if (o == 1)
                                    t = (x + y) << 1;

                                if (o == 2)
                                    t = (x << 1) + y;

                                up(f[i][j][r][k][1][0], w + t);
                            }
                        }

    for (j = 0; j <= cb; j++)
        for (o = 0; o < 3; o++)
            up(ans, f[ca][j][j][cc][cd][o]);
}
void cal() {
    sort(c + 1, c + cc + 1, cmpz);
    solve();
    sort(c + 1, c + cc + 1, cmpx);
    solve();
}
int main() {
    scanf("%d", &n);

    for (i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].z = a[i].x + a[i].y;
    }

    if (a[n].x == 10) {
        n++;
        flag = 1;
        scanf("%d%d", &a[n].x, &a[n].y);
        a[n].z = a[n].x + a[n].y;
    }

    for (i = 1; i <= n; i++) {
        if (a[i].x == 10) {
            ca++;
            continue;
        }

        if (a[i].z == 10) {
            b[++cb] = a[i];
            continue;
        }

        c[++cc] = a[i];
    }

    sort(b + 1, b + cb + 1, cmpx);
    cal();

    for (i = 1; i <= cc; i++) {
        cd = 1, d = c[i];

        for (j = 1; j <= cc; j++)
            _c[j] = c[j];

        for (_ = 0, j = 1; j <= cc; j++)
            if (j != i)
                c[++_] = c[j];

        cc = _;
        cal();

        for (cc++, j = 1; j <= cc; j++)
            c[j] = _c[j];
    }

    return printf("%d", ans), 0;
}

代码说明

关键数据结构

• Round 结构体：存储每轮的得分信息
• 分类数组：
  • a[]：所有轮次
  • b[]：补中轮次
  • c[]：失误轮次
  • d：特殊轮次

DP状态含义

f[i][j][r][k][S][o] 表示：

• i：已使用的全中轮数
• j：从左使用的补中轮数
• r：从右使用的补中轮数
• k：已使用的失误轮数
• S：特殊轮使用标记
• o：翻倍状态（0-无,1-全翻倍,2-第一次翻倍）

算法亮点

1. 双向使用补中轮：从左和从右分别使用，探索更多排列可能
2. 多种排序策略：对失误轮尝试不同排序方法
3. 特殊轮枚举：将每个失误轮作为特殊轮单独处理
4. 翻倍状态跟踪：精确记录不同轮次对后续的影响

复杂度分析

• 时间复杂度：$O(n^5)$，在 $n \leq 50$ 时可接受
• 空间复杂度：$O(n^4)$