题目

有n个矩阵，大小分别为 $a[0]$ ∗ $a[1]$ , $a[1]$ ∗ $a[2]$ , $a[2]$ ∗ $a[3]$ , ... , $a[n1]$ ∗ $a[n]$ ，现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。（ $2 \le n \le 1000$ , $a[i] \le 100$ ）

两个大小分别为 $p$ ∗ $q$ 和 $q$ ∗ $r$ 的矩阵相乘时的运算次数计为 $p$ ∗ $q$ ∗ $r$ 。

注意不同的运算顺序会导致运算次数不一样，以样例为例：

如果我们先算前两个矩阵的乘积，将运算 $1$ ∗ $10$ ∗ $5$ = $50$ 次，并得到一个 $1$ ∗ $5$ 的矩阵，之后再算这个 $1$ ∗ $5$ 的矩阵和最后一个 $5$ ∗ $20$ 的矩阵的乘积，将运算 $1$ ∗ $5$ ∗ $20$ = $100$ 次，共运算 $150$ 次；

如果我们先算后两个矩阵的乘积，将运算 $10$ ∗ $5$ ∗ $20$ = $1000$ 次，并得到一个 $10$ ∗ $20$ 的矩阵，之后再算第一个 $1$ ∗ $10$的矩阵和 $10$ ∗ $20$ 的矩阵的乘积，运算 $1$ ∗ $10$ ∗ $20$ = $200$ 次，共运算 $1200$ 次。

输入

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

输出

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

数据范围

$10$

$30$

$60$

$100$ , $a[i] \le 100$

输入样例

输入样例1：

3
1 10 5 20

输出样例

输出样例1：

150

样例解释

不同的运算顺序会导致运算次数不一样，以样例为例：

如果我们先算前两个矩阵的乘积，将运算 $1$ * $10$ * $5$ = $50$ 次，并得到一个 $1$ * $5$ 的矩阵，之后再算这个 $1$ * $5$ 的矩阵和最后一个 $5$ * $20$ 的矩阵的乘积，将运算 $1$ * $5$ * $20$ = $100$次，共运算 $150$ 次。

如果我们先算后两个矩阵的乘积，将运算 $10$ * $5$ * $20$ = $1000$ 次，并得到一个 $10$ * $20$ 的矩阵，之后再算第一个 $1$ * $10$ 的矩阵和这个 $10$ * $20$ 的矩阵的乘积，运算 $1$* $10$ * $20$ = $200$ 次，共运算 $1200$ 次。

我的 连样例都没过 的代码

#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