poj 1651 Multiplication Puzzle 区间DP 矩阵连乘最优次序

缘起

日常浪费生命~ poj 1651 Multiplication Puzzle

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给出一组N个数，每次从中抽出一个数（第一和最后一个不能抽），该次的得分即为抽出的数与相邻两个数的乘积。直
到只剩下首尾两个数为止。问最小得分是多少？

【输入】
第一行是N(3 <= N <= 100).然后是N行，每行的数字在1~100之间 

【输出】
最小得分

【样例输入】
6
10 1 50 50 20 5

【样例输出】
3650

【限制】
1s

典型的区间DP问题. 其实就是矩阵最优乘法次序问题（n*m矩阵和m*p矩阵相乘的乘法次数就是n*m*p）. 所以本题其实就是求矩阵连乘按照什么次序复杂度最小（注意, 矩阵乘法不具备交换律，但是具备结合律）.

1
2
3
首先将原问题转换为矩阵连乘问题. 然后令
dp[i,j]是第i个矩阵到第j个矩阵连乘最少的乘法次数(0<i<j<n-1).
则dp[i,i+1]=就是相邻矩阵的乘法次数, dp[i,i]=0

这里总结一下区间DP问题的典型特征——它的DP公式都是抽中间某个元素（例如【1】）.

而且，和【1】一样，我dp个屁~ 数据规模这么小, 肯定记忆化搜索啊~

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n, a[105], dp[105][105], flag[105][105];

struct matrix
{
	int a,b; // a*b矩阵
}m[105];

int rec(int i, int j) // m[i,...,j]连乘的最小乘法次数, 用记忆化搜索
{
	if (flag[i][j])
	{
		return dp[i][j];
	}
	int ans = 0x3f3f3f3f;
	for (int k = i; k<j; k++) // 最后是m[i,..,k]*m[k+1,..,j], 乘法次数是m[i].a*m[k].b*m[j].b
	{
		ans = min(ans, rec(i,k)+rec(k+1,j)+m[i].a*m[k].b*m[j].b);
	}
	flag[i][j] = true;
	return dp[i][j] = ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	scanf("%d", &n);
	for (int i = 0;i<n;i++)
	{
		scanf("%d", a+i);
	}
	for (int i = 0;i<n-1;i++)
	{
		m[i].a = a[i];
		m[i].b = a[i+1];
	} // 转换为n-1个矩阵连乘问题
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 0; i<n-1; i++)
	{
		dp[i][i] = 0;
		flag[i][i] = true;
	}
	for (int i = 0;i<n-2; i++)
	{
		dp[i][i+1] = m[i].a*m[i].b*m[i+1].b;
		flag[i][i+1] = true;
	}
	printf("%d\n", rec(0,n-2));
	return 0;
}

ac情况

Status Accepted
Memory 204kB
Length 992
Lang C++
Submitted 2019-09-20 12:23:41
Shared
RemoteRunId 20878006

参考

【1】https://yfsyfs.github.io/2019/09/12/poj-1179-Polygon-%E5%A4%9A%E8%BE%B9%E5%BD%A2%E6%B8%B8%E6%88%8F-%E5%8C%BA%E9%97%B4DP/