Toggle navigation
C语言网
教程
博客
团队
训练
训练
题库
题集
状态
排名
比赛
比赛
标准
自主
考试
网课
AI助手
AI助手
代码解释
语言转换
编程助手
梦里京华
私信TA
用户名:508304482
访问量:7711
签 名:
等 级
P4
排 名
856
经 验
3450
参赛次数
4
文章发表
18
年 龄
0
在职情况
学生
学 校
XJTU
专 业
自我简介:
TA的其他文章
数据结构-采用十字链表存储的稀疏矩阵-题解(C++代码)
浏览:
270
数据结构-线索二叉树-题解(C++代码)
浏览:
383
数据结构-自底向上的赫夫曼编码-题解(C++代码)
浏览:
671
你可能喜欢
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)
浏览:
2662
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)
浏览:
1252
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)
浏览:
528
素数判断模板题(题解中的函数能用来判断大数是不是素数)
浏览:
841
【绝对值排序】 (C语言代码)
浏览:
481
蓝桥杯算法提高VIP-矩阵乘法 (C++代码)
作者:
梦里京华
发表时间:2020-03-13 18:13:33
浏览:526 | 评论: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
#include
#include
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 人评分
分享
收藏
动态规划
C语言网推出会员服务,提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源,享受丰富的技术学习到变现的乐趣,
以含金量和学习效果勇敢挑战同类辅导
! 点击了解开通
评论区
«
»
提交
精彩推荐
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)
浏览:
687
C语言训练-求矩阵的两对角线上的元素之和 (C语言代码)
浏览:
700
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)
浏览:
976
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)
浏览:
564
C语言程序设计教程(第三版)课后习题8.1 (Java代码)
浏览:
774
打水问题 (C语言代码)
浏览:
1063
简单的a+b (C语言代码)
浏览:
596
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)
浏览:
1294
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)
浏览:
904
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)
浏览:
470
有问题
,
问问AI
代码解释
语言转换
编程助手