刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

靶场上有n块靶排成一排，从左到右依次编号为1、2、3、….n，且每块靶上都标有一个整数。

当某块靶被击中后，击中者会得到 x * y * z 的积分。( y 表示被击中的靶上的数，x表示其左侧最近且未被击中的靶上的数，z表示其右侧最近且未被击中的靶上的数。如果其左侧不存在未被击中的靶，则x为1；如果其右侧不存在未被击中的靶，则z为1。）

计算完积分后，这块靶就会退出靶场（不在这排靶中）。

请计算击中所有靶后能得到的最高积分是多少？

例如：n=4，表示有4块靶，这4块靶上的数从左到右分别是3、2、4、6;

按照下列顺序打靶，可以得到最高积分：

1.打2号靶，得到的积分是24（3*2*4）；

2.打3号靶，得到的积分是72（3*4*6）；

3.打1号靶，得到的积分是18（1*3*6）；

4.打4号靶，得到的积分是6（1*6*1）；

最终获得的积分是120（24+72+18+6）。

输入描述

第一行输入一个整数n（1≤n≤300），表示靶场上靶的数量

第二行输入n个整数（1≤整数≤100），分别表示从左到右每块靶上的数，整数之间以一个空格隔开

输出描述

输出一个整数，表示击中所有靶后能得到的最高积分


样例输入

4
3 2 4 6

样例输出

120

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```#include #include #include using namespace std;int main() int n;cin >> n;vector nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}long long total_score = 0;vector left_max(n, 0);vector right_max(n, 0);left_max[0] = nums[0];for (int i = 1; i < n; i++) {left_max[i] = max(left_max[i - 1], nums[i]);}right_max[n - 1] = nums[n - 1];for (int i = n - 2; i >= 0; i--) {right_max[i] = max(right_max[i + 1], nums[i]);}for (int i = 0; i < n; i++) {long long score = (i == 0 ? 1 : left_max[i - 1]) * nums[i] * (i == n - 1 ? 1 : right_max[i + 1]);total_score += score;}cout << total_score << endl;return 0;```

解析：

【喵呜刷题小喵解析】：

这个问题可以通过动态规划来解决。首先，我们需要计算每个位置左侧和右侧的最大值，以便计算击中该靶时的积分。

我们可以定义两个数组`left_max`和`right_max`，其中`left_max[i]`表示第`i`个位置左侧未被击中的靶的最大值，`right_max[i]`表示第`i`个位置右侧未被击中的靶的最大值。

然后，我们可以遍历每个位置，计算击中该靶时的积分，并将其累加到总积分中。击中第`i`个靶时的积分为`(i == 0 ? 1 : left_max[i - 1]) * nums[i] * (i == n - 1 ? 1 : right_max[i + 1])`，其中`(i == 0 ? 1 : left_max[i - 1])`表示第`i`个靶左侧未被击中的靶的最大值，`nums[i]`表示第`i`个靶上的数，`(i == n - 1 ? 1 : right_max[i + 1])`表示第`i`个靶右侧未被击中的靶的最大值。

最后，输出总积分即可。

注意，由于积分的值可能很大，我们需要使用`long long`类型来存储积分。
创作类型：
原创

本文链接：靶场上有n块靶排成一排，从左到右依次编号为1、2、3、….n，且每块靶上都标有一个整数。 当某块靶被

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share