POJ 1651. Multiplication Puzzle

Author: 2015-10-09

ACM

, ,

1. 题目

http://poj.org/problem?id=1651

Multiplication Puzzle
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 7404 Accepted: 4581

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

10*1*50 + 50*20*5 + 10*50*5 = 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

1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150.

Input

The first line of the input contains the number of cards N (3 <= N <= 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

6
10 1 50 50 20 5

Sample Output

3650

Source

Northeastern Europe 2001, Far-Eastern Subregion

2. 思路

给出一个长度为N的数字序列，从中取出一个数字，得分为该数字与其左右相邻两个数字的乘积，反复抽取并累计分数，直到只剩下两个数字，求最小分数。

区间DP。记原始序列中第i个数字为num[i]，记从i到j区间内数字序列为子序列(i, j)，使用f[i][j]表示子序列(i, j)所能达到的最小分数，索引计数从0开始，有：

for len = 3 : N
    for start = 0 : N - len + 1
        end = start + len - 1
        if len == 3:
            f[start][end] = num[start]* num[start + 1] * num[end]
        else:
            f[start][end] = MAX
            for mid = start + 1 : end - 1:
                f[start][end] = min(
                        f[start][mid] + f[mid][end] + num[start] * num[mid] * num[end], 
                        f[start][mid])

对于长度为3的子序列，有且只有唯一得分数。对于长度大于3的子序列，假设最后一次抽取数字为num[mid]，则总分数为前半段分数f[start][mid]，加上后半段分数f[mid][end]，再加上最后一次抽取num[mid]的分数num[start] * num[mid] * num[end]，遍历所有mid找最小值。

3. 代码

#include <cstdio>

const int MAX_N = 100 + 1;
const int MAX = 0x0fffffff;

void solveE7d_MultiplicationPuzzle();
int input(int num[]);

int main() {
	//freopen("test.txt", "r", stdin);
	solveE7d_MultiplicationPuzzle();
}

int num[MAX_N];
int f[MAX_N][MAX_N];
void solveE7d_MultiplicationPuzzle() {
	int n = input(num);

	for (int len = 1; len <= n - 2; ++len) {
		for (int start = 0; start + len + 1 < n; ++start) {
			int end = start + len + 1;
			if (len == 1) {
				f[start][end] = num[start]* num[start + 1] * num[end];
			} else {
				f[start][end] = MAX;
				for (int i = start + 1; i < end; ++i) {
					int cand = f[start][i] + f[i][end] + num[start] * num[i] * num[end];
					f[start][end] = f[start][end] < cand ? f[start][end] : cand;
				}
			}
		}
	}

	printf("%d\n", f[0][n - 1]);
}

int input(int num[]) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &num[i]);
	}
	return n;
}