Poj1651 Multiplication Puzzle

发表于 | 更新于: | 分类于 ， ， | | 阅读数
字数统计: 600 | 阅读时长 ≈ 3

Description

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row. The goal is to take cards in such order as to minimize the total number of scored points. For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring $10150 + 50205 + 10505 = 500+5000+2500 = 8000 $.If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be $15020 + 1205 + 1015 = 1000+100+50 = 1150$.

Input

The first line of the input contains the number of cards $N (3 \leq N \leq 100)$. The second line contains N integers in the range from 1 to 100, separated by spaces.

Output

Output must contain a single integer - the minimal score.

Sample Input

1
2
6
10 1 50 50 20 5

Sample Output

1
3650

Analysis

一列数字，每次从中取出一个数字（不能是第一个或最后一个），得分是这个数字与它前后两边数字的乘积，一直取到还剩下两个数字，求可以得到的最小的分数。

可以采用区间DP的做法，从最小的区间（3个数字）开始，逐步扩大区间，用dp数组存储每个区间可以得到的最小的分数，最后得到整个区间可以得到的最小的分数。

用dp[i][j]表示区间i-1到j可以获得的最小的分数，则递推式

$dp[i][j]=\min(dp[i][j],dp[i][k]+dp[k+1][j]+card[i-1]\times card[k]\times card[j])$;表示当最后一次取的是第k个时，k之前与k之后区间的最小得分与取第k个时它与该区间开头与结尾的分的乘积的和（因为左右区间都取过了），就是当前区间可以得到的最小得分。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int card[105];
int dp[105][105];
int main()
{
	while (cin >> N)
	{
		for (int i = 0; i < N; i++)
		{
			cin >> card[i];
		}
		memset(dp, 0, sizeof(dp));
		for (int len = 1; len < N; len++)
		{
			int i, j, k;
			for (i = 1, j = len + 1; j < N; i++, j++)
			{
				int min = 9999999;
				for (k = i; k < j; k++)
				{
					int count = dp[i][k] + dp[k + 1][j] + card[i - 1] * card[k] * card[j];
					if (count < min)
						min = count;
					dp[i][j] = min;
				}
			}
		}
		cout << dp[1][N - 1] << endl;
	}
	return 0;
}