删数问题

问题描述

现有\(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

4
3 4 5 6

样例输出1

192

样例输入2

5
3 6 7 8 2

样例输出2

528

解析

问题分析

一个典型的区间动规。

状态：
\(dp[i][j]\)表示第\(i\)个数字到第\(j\)个数字，假设最后删掉\(k\)个数得到的结果最大

状态转移方程：

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

代码

C++

#include <bits/stdc++.h>
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<=n;i++)
	{
		cin >> a[i];
	}
	for(int r=3;r<=n;r++)
	{
		for(int i=1;;i++)
		{
			int j=i+r-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[k]*a[j]);
			}
			if(j>=n) 
			{
				break;
			}
		}
	} 
	cout << dp[1][n];
	return 0;
}