BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（小学高年级组） 第 18 题

第 3 题

#include <cstdio>
#include <cstring>
using namespace std;

int n, a[35], rt[35][35], val[35][35];

long long calc(int l, int r) {
    if (l > r)
        return 1;
    if (val[l][r] != -1)
        return val[l][r];
    if (l == r) {
        val[l][r] = a[l];
        rt[l][r] = l;
    }
    else {
        for (int i = l; i <= r; i++)
            if (calc(l, i - 1) * calc(i + 1, r) + a[i] > val[l][r]) {
                val[l][r] = calc(l, i - 1) * calc(i + 1, r) + a[i];
                rt[l][r] = i;
            }
    }
    return val[l][r];
}

void output(int l, int r) {
    if (r < l)
        return;
    printf("%d ", rt[l][r]);
    output(l, rt[l][r] - 1);
    output(rt[l][r] + 1, r);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    memset(val, -1, sizeof(val));
    printf("%lld\n", calc(1, n));
    output(1, n);
    r

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

本题考查基础知识的理解与应用，需要结合所学概念进行分析和判断。

注意审题，看清题目要求是选择"正确的"还是"不正确的"。逐一分析每个选项，排除明显错误的选项。

核心概念：本题涉及计算机科学基础知识，需要准确理解相关概念的定义和应用场景。

推导分析：逐一检查每个选项是否符合题目的条件和要求；对于不确定的选项，可以尝试举反例验证；结合排除法缩小选择范围。

避坑指南：注意否定词如"不正确的是""不属于"；注意限定词如"一定""可能""必须"等绝对化表述往往是陷阱。

解题技巧：先排除明显错误的选项，在剩余选项中仔细比较。对于计算题，列出公式仔细计算。