解题思路

剩余序列始终是原数组的一段连续区间，因此用区间 DP。

设 $dp[i][j]$ 表示把 $a[i..j]$ 全部删完的最小代价。
区间长度为 $1$ 时，当前长度是 $1$ ，有 $dp[i][i]=a[i]$ 。
区间长度为 $len=j-i+1$ 时，第一步只能删左端 $a[i]$ 或右端 $a[j]$ ： $dp[i][j]=\min\bigl(len\cdot a[i]+dp[i+1][j],\ len\cdot a[j]+dp[i][j-1]\bigr)$

题目内容

给定长度为 $n$ 的正整数数组 $a$ 。每次只能删除当前序列最左或最右的元素；若当前长度为 $\textit{len}$ 、被删元素值为 $x$ ，则此次代价为 $\textit{len}\times x$ 。求将数组全部删完的最小总代价。

第一行一个整数 $n$ 。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$ 。

输出一个整数，表示最小总代价。

输入：

4
2 2 1 2

输出：

说明：一种最优顺序是先删右端 $2$ （代价 $8$ ），再删右端 $1$ （代价 $3$ ），再删一端的 $2$ （代价 $4$ ），最后删剩下的 $2$ （代价 $2$ ），总代价 $8+3+4+2=17$ 。

选择提交后点击「开始AI分析」