梦里京华

用户名：508304482

访问量：8700

签　名：

等　　级
排　　名	876
经　　验	3561
参赛次数	4
文章发表	18
年　　龄	0
在职情况	学生
学　　校	XJTU
专　　业

　　自我简介：

TA的其他文章

数据结构-行编辑程序-题解(C++代码)
浏览：345

数据结构-表达式求值-题解(C++代码)
浏览：289

数据结构-求子串位置的定位函数-题解(C++代码)
浏览：225

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C++代码）

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

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

　　作者: 梦里京华　　　　发表时间：2020-03-13 18:13:33 浏览：570　|　评论：0　

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

###### 与合并石子那题有点类似

定义 dp[i][j]：第i个矩阵依次乘到第j个矩阵的最少的运算次数；
定义 A[i][j]：第i个矩阵依次乘到第j个矩阵所得的矩阵

那么 A[i][j]=A[i][k]*A[k+1][j]       (k=i to j-1)
这样将在k从i遍历到j-1的过程中,更新dp[i][j]的值。

即转态转移方程为：
###### dp[i][j] = min{  dp[i][j] , dp[i][k] + dp[k + 1][j] + a[i]a[k + 1]a[j + 1]  }
注意初始化dp[i][j]的值。
###### 结果有可能超过int的范围注意
(我的代码写得有点丑）

```cpp
#include <string.h>
#include<iostream>
#include <stdio.h>
const long long inf = 100000000000001;
long long dp[1003][1003], a[1003], n;
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            dp[i][j]=inf;
        }
    }
    for (int i = 1; i <= n + 1; ++i)
    {
        dp[i][i] = 0;
        scanf("%d", &a[i]);
    }
    for (int p = 1; p < n; ++p)
    {
        for (int i = 1; i <= n - p; ++i)
        {
            int j = i + p;
            for (int k = i; k < j; ++k)
            {
                long long  q1 = dp[i][j];
                long long  q2 = dp[i][k] + dp[k + 1][j] + a[i] * a[k + 1] * a[j + 1];
                dp[i][j] = q1 > q2 ? q2 : q1;
            }
        }
    }
    printf("%lld\n", dp[1][n]);
    return 0;
}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

梦里京华

TA的其他文章

你可能喜欢

C二级辅导-公约公倍（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C++代码）

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

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

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

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

评论区

精彩推荐

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

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

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

妹子杀手的故事（C语言代码）

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

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

矩阵加法（C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

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

陈教主的三角形（C语言代码）

梦里京华

TA的其他文章

你可能喜欢

C二级辅导-公约公倍 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C++代码）

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

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

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

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

评论区

精彩推荐

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

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

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

妹子杀手的故事 （C语言代码）

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

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

矩阵加法 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

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

陈教主的三角形 （C语言代码）

C二级辅导-公约公倍（C语言代码）

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

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

　　评论区

妹子杀手的故事（C语言代码）

矩阵加法（C语言代码）

陈教主的三角形（C语言代码）