刪數問題

問題描述

現有\(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;
} 

本文來自小默的博客，轉載請註明原文鏈接：https://www.cnblogs.com/momotrace/p/nonumproblem.html