靶场上有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
正确答案：参考程序（Python）：打靶积分。区间DP：dp[i][j]打空(i,j)内所有靶最高积分，取最后一个打的靶k，dp[i][j]=max(dp[i][k-1]+dp[k+1][j]+a[i-1]*a[k]*a[j+1])。样例3 2 4 6→120。核心：区间DP打靶。
试卷来源：202403(第15届)蓝桥杯C++编程青少组(选拔赛_中高级)真题