squanchy

用户名：uq_11086648109

访问量：1318

签　名：

等　　级
排　　名	16639
经　　验	753
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

基于动态规划思路的拿糖果解题方案
浏览：653

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

蓝桥杯算法提高VIP-矩阵乘法（C++代码）

　　作者: squanchy　　　　发表时间：2020-02-24 00:27:23 浏览：523　|　评论：1　

原题链接：蓝桥杯算法提高VIP-矩阵乘法

这道题不能采用贪心法，因为如果每次让所用乘法次数最少的两矩阵相乘，最终所得结果不一定为最优解，例如<10,100>，<100,1>，<1,1>这三个矩阵，采用贪心法算得结果为1100，而最优解为1010。
  
针对本题我提出了这样的思路:n个矩阵相乘，简记为a1.a2.a3...an(ai代表第i个矩阵)，可拆分为a1.(a2.a3.a4...an)、（a1.a2）.(a3.a4.a5...an)、(a1.a2.a3).(a4.a5.a6...an)，也就是说将n个矩阵使用结合律划分为两部分aL,aR(L、R可以理解为左右),那个使得aR内部乘法次数+aL乘法次数+aR乘aL的乘法次数最小的划分方法就是使得a1.a2.a3...an所用乘法次数最小的方法，即本题所求的最优解。

aR、aL内部的最小乘法次数同理，也是根据上述方法计算，算n个矩阵要计算aR、aL;而算aR、aL又要计算更小的结构，不断递归向下，直到最后只有两个矩阵时便能够直接相乘，两个矩阵相乘的最小乘法次数=两个矩阵唯一相乘方法的乘法次数，将这个过程逆转就是动态规划的解题过程:算两两相乘的乘法次数，在此基础上计算三个矩阵连续相乘的乘法次数最小值，一直到n个矩阵相乘的乘法次数最小值，。

记x[i].a、x[i].b分别为n个矩阵的行数、列数，dp[i][j]为n个矩阵中第i个到第j个相乘的乘法次数最小值,record[i][j].a、record[i][j].b分别为n个矩阵中第i个到第j个相乘所得新矩阵的行数和列数，现对dp、record数组做如下初始化:
```cpp
dp[i][i]=0;  //(i=1...n) 因为自己不需要乘自己
dp[i][i+1]=x[i].a*x[i].b*x[i+1].b  //(i=1...n-1)
record[i][i+1].a=x[i].a; record[i][i+1].b=x[i+1].b;  //(i=1...n-1)
record[i][i].a=x[i].a; record[i][i].b=x[i].b;  //(i=1...n)
```
代码如下:
```cpp
#include<iostream>
#include<vector>
#include<string.h>
#include <algorithm>
using namespace std;
typedef struct matrix
{
	int a, b;
};
int main()
{
	int n;
	cin >> n;
	matrix* x = new matrix[n + 1];//下标从1开始
	int** dp = new int* [n + 1];
	matrix** record = new matrix * [n + 1];
	for (int i = 1; i <= n; i++)
	{
		dp[i] = new int[n + 1];
		record[i] = new matrix[n + 1];
	}
	//输入
	cin >> x[1].a;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i].b;
		if (i != n)
			x[i + 1].a = x[i].b;
	}
	
	//初始化
	for (int i = 1; i <= n - 1; i++)
	{
		dp[i][i + 1] = x[i].a * x[i].b * x[i + 1].b;
		record[i][i + 1].a = x[i].a;
		record[i][i + 1].b = x[i + 1].b;
	}
	for (int i = 1; i <= n; i++)
	{
		dp[i][i] = 0;
		record[i][i].a = x[i].a;
		record[i][i].b = x[i].b;
	}
	
	//从三连续相乘开始计算，直到n连续相乘
	int from, to;
	int num_min;
	int it;
	int t, i, j,t_1;
	int n_2 = n + 2;
	for (t = 3; t < n+1; ++t)//t表示本次要计算t个连续矩阵相乘所用的最小乘法次数
	{
		it = n_2 - t;
		t_1 = t - 1;
		for (i = 1; i <it; ++i)
		{
			from = i;
			to = i + t_1;
			num_min = 2147483647;
			for (j = from; j < to; ++j)
			{
				int j_1 = j + 1;
				int c = dp[from][j] + dp[j_1][to] + record[from][j].a * record[from][j].b * record[j_1][to].b;
				if (num_min > c)
				{
					num_min = c;
				}
			}
			dp[from][to] = num_min;
			record[from][to].a = x[from].a;
			record[from][to].b = x[to].b;
		}
	}
	cout << dp[1][n];
	return 0;
}
```
这个代码提交后显示时间超限65%，在矩阵数目的上限:1000的情况下,我自己在IDE里的运行时长是秒级的，但是无法优化到1秒以内，尽管考虑了很多方面，例如尽量将循环内层里的运算放到外层，使用<而不是<=，使用++i而不是i++等，还是无法有效地优化运行时长，期待有高手能够改进这一思路或是提出一种更高效的思路。

0.0分

2 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

Mr影

我采用了区间dp的方法，在矩阵数目1000的情况下，只能做到时间超限18%，没有办法继续优化了

2020-03-08 20:41:25

squanchy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C二级辅导-等差数列（C++代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

【绝对值排序】（C语言代码）

蓝桥杯算法提高VIP-矩阵乘法（C++代码）

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【回文数(二)】（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

WU-格式化数据输出（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

squanchy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C二级辅导-等差数列 （C++代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

【绝对值排序】 （C语言代码）

蓝桥杯算法提高VIP-矩阵乘法 （C++代码）

评论区

精彩推荐

C语言训练-委派任务* （C语言代码）..................竟然是第一个

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【回文数(二)】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

WU-格式化数据输出 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C二级辅导-等差数列（C++代码）

【绝对值排序】（C语言代码）

蓝桥杯算法提高VIP-矩阵乘法（C++代码）

　　评论区

【回文数(二)】（C语言代码）

WU-格式化数据输出（C语言代码）