删数问题

问题描述

现有\(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\)个数得到的结果最大

状态转移方程:

\[dp[i][j]=dp[i][k]+dp[k][j]+a[i]×a[k]×a[j]; \]

对于第\(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;
} 

热门相关:亿万盛宠只为你   拒嫁豪门,前妻太抢手   不科学御兽   异世修真邪君   重生之嫡女祸妃