社区讨论

区间dp求助，站外题

LLucaZSC
学术版参与者 4已保存回复 19

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
19 条
当前快照
1 份
快照标识符
@lo8eie12
此快照首次捕获于
2023/10/27 17:18
2 年前
此快照最后确认于
2023/10/27 17:18
2 年前
查看原帖

题目

有n个矩阵，大小分别为 a[0]a[0] ∗ a[1]a[1] , a[1]a[1] ∗ a[2]a[2] , a[2]a[2] ∗ a[3]a[3] , ... , a[n1]a[n1] ∗ a[n]a[n] ，现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。（ 2≤n≤10002 \le n \le 1000 , a[i]≤100a[i] \le 100 ）
两个大小分别为 pp ∗ qq 和 qq ∗ rr 的矩阵相乘时的运算次数计为 pp ∗ qq ∗ rr 。
注意不同的运算顺序会导致运算次数不一样，以样例为例：
如果我们先算前两个矩阵的乘积，将运算 11 ∗ 1010 ∗ 55 = 5050 次，并得到一个 11 ∗ 55 的矩阵，之后再算这个 11 ∗ 55 的矩阵和最后一个 55 ∗ 2020 的矩阵的乘积，将运算 11 ∗ 55 ∗ 2020 = 100100 次，共运算 150150 次；
如果我们先算后两个矩阵的乘积，将运算 1010 ∗ 55 ∗ 2020 = 10001000 次，并得到一个 1010 ∗ 2020 的矩阵，之后再算第一个 11 ∗ 1010的矩阵和 1010 ∗ 2020 的矩阵的乘积，运算 11 ∗ 1010 ∗ 2020 = 200200 次，共运算 12001200 次。

输入

第一行输入一个整数n，表示矩阵的个数。 第二行输入 n+1n+1 个数，表示给定的矩阵。

输出

输出一个整数，表示最少的运算次数。

数据范围

1010% 2 \le n \le 10
3030% 2 \le n \le 50
6060% 2 \le n \le 100
100100% 2 \le n \le 1000 , a[i]≤100a[i] \le 100

输入样例

输入样例1：
CPP
3
1 10 5 20

输出样例

输出样例1：
CPP
150

样例解释

不同的运算顺序会导致运算次数不一样，以样例为例：
如果我们先算前两个矩阵的乘积，将运算 11 * 1010 * 55 = 5050 次，并得到一个 11 * 55 的矩阵，之后再算这个 11 * 55 的矩阵和最后一个 55 * 2020 的矩阵的乘积，将运算 11 * 55 * 2020 = 100100次，共运算 150150 次。
如果我们先算后两个矩阵的乘积，将运算 1010 * 55 * 2020 = 10001000 次，并得到一个 1010 * 2020 的矩阵，之后再算第一个 11 * 1010 的矩阵和这个 1010 * 2020 的矩阵的乘积，运算 11* 1010 * 2020 = 200200 次，共运算 12001200 次。
我的 连样例都没过 的代码
CPP
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
using namespace std;
long long n,a[205],dp[205][205],b[205];
int main(){
	cin>>n;
	memset(dp,0x3f,sizeof(dp));
	memset(b,1,sizeof(b)); 
	for(int i=1;i<=n+1;i++){
		cin>>a[i];
		b[i]=b[i-1]*a[i];
		dp[i][i]=1;
	}
	for(int i=2;i<=n+1;i++){
		for(int l=1,r=l+i-1;r<=n+1;l++,r++){
			for(int j=l;j<r;j++){
				dp[l][r]=min(dp[l][j]+dp[j+1][r]+a[l]*a[j]*a[r],dp[l][r]);
			}
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}
顺便一提，发帖时输入有Bug

回复

共 19 条回复，欢迎继续交流。

正在加载回复...