删数问题

问题描述

现有\(n\)个正整数组成的序列\(a\)，从中删除一个数，得分是其本身同左、右相邻的数的乘积，
然后再在剩余的整数中继续删除，注意序列两端的数字a1和an是不能删除的，求这样删除\(n-2\)个整数后的最大得分。
例如有四个数\(3 、4、5、6\)，按照先\(4\)后\(5\)的删除顺序，其得分为\(345+356=150\)，
按照先\(5\)后\(4\)的删除顺序，其得分为\(456+346=192\)，因此最大得分为\(192\)。
输入格式

第一行一个整数\(n\)
接下来\(n\)个正整数表示序列\(a\)
输出格式

一个正整数表示删除\(n-2\)个整数后的最大得分
样例

样例输入1

1. 4
2. 3 4 5 6

复制代码

样例输出1

1. 192

复制代码

样例输入2

1. 5
2. 3 6 7 8 2

复制代码

样例输出2

1. 528

复制代码

解析

问题分析

一个典型的区间动规。
状态：
\(dp[j]\)表示第\(i\)个数字到第\(j\)个数字，假设最后删掉\(k\)个数得到的结果最大
状态转移方程：

\[dp[j]=dp[k]+dp[k][j]+a×a[k]×a[j];\]
对于第\(i\)个物品到第\(j\)个物品，假设最后删掉\(k\)得到的结果最大，那么最后一次删除时，得到的分数就是 \(a × a[k] × a[j]\)。那么总的得分就是需要加上之前删掉\(k\)的左右两边除了\(i，j\)之外所有数的和，即\(dp[j]\) 的两个子问题，分别是\(dp[k]\) 和\(dp[k][j]\)。由此便可得出上面所写的状态转移方程
代码

C++

[code]#include using namespace std;int a[1010];//用来保存序列 int dp[1010][1010];//i、j用来保存删除第i个数到第j个数所得到的最优值 int main(){        int n;        cin >> n;        for(int i=1;i> a;        }        for(int r=3;r