A25784. 靶场上有n块靶排成一排，从左到右依次编号为1、2、3、….n，且每块靶上都标有一个整数。当某块靶被击中后，击中者会得到 x * y * z 的积分。( y 表示被击中的靶上的数，x表示其左侧最近且未被击中的靶上的数，z表示其右侧最近且未被击中的靶上的数。如果其左侧不存在未被击中的靶，则x为1；如果其右侧不存在未被击中的靶，则z为1。）计算完积分后，这块靶就会退出靶场（不在这排靶中）。请计算击中所…
填空题
中等
知识点
题目描述
靶场上有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 <bits/stdc++.h>
using namespace std;
int a[305], dp[305][305];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
a[0] = a[n + 1] = 1; // 左右双端各补一个1，这两个点不打
for (int ls = 1; ls <= n; ls++) // 枚举区间长度从1开始
for (int i = 0, j; i <= n - ls; i++) { // 区间开始点
j = i + ls + 1; // 区间结束点
for (int k = i + 1; k <= j - 1; k++) {
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[j] * a[k]);
}
}
cout << dp[0][n + 1];
return 0;
}
上一题
下一题