UVAoj 348 - Optimal Array Multiplication Sequence

简介:
 1 /*
 2     题意:矩阵相乘的最少的步数
 3     dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+num[i-1]*num[k]*num[j]);
 4     表示的是第i个矩阵到第j个矩阵相乘的最少步数
 5     sign[i][j]表示的是第i个矩阵到第j个矩阵相乘的最少步数是由第i个矩阵到第sign[i][j]个矩阵相乘最少步数
 6     和第sign[i][j]+1个矩阵到第j个矩阵相乘最少步数的得到的最小值!
 7 */
 8 #include<iostream>
 9 #include<cstring>
10 #include<string>
11 #include<cstdio>
12 #include<algorithm>
13 using namespace std;
14 int dp[15][15];
15 int sign[15][15];
16 int num[15];
17 int ld[15], rd[15];
18 int n;
19 
20 void dfs(int l, int r){//将[l,r]不断分解成最优的子区间
21     if(sign[l][r]==0) return ;
22     ld[l]++;//l数字出现了多少次,就意味着出现了多少次区间作值为l,也就是出现了多少次左括号
23     rd[r]++;//同理r右侧出现了多少次右括弧
24     dfs(l, sign[l][r]);
25     dfs(sign[l][r]+1, r);
26 }
27 
28 void traceBack(){
29  
30    memset(ld, 0, sizeof(ld));
31    memset(rd, 0, sizeof(rd));
32    dfs(1, n);
33    for(int i=1; i<=n; ++i){
34        while(ld[i]--) cout<<"(";
35        cout<<"A"<<i;
36        while(rd[i]--) cout<<")";
37        if(i!=n)
38          cout<<" x ";
39    }
40    cout<<endl;
41 }
42 
43 void traceBackTmp(int l, int r){//这是用递归的形式写的,将区间不断缩小,打印(Ai x Aj)
44    if(l>r) return;
45    if(l==r)  printf("A%d", l);
46    else{
47       printf("(");
48       traceBackTmp(l, sign[l][r]);
49       printf(" x ");
50       traceBackTmp(sign[l][r]+1, r);
51       printf(")");
52    }
53 }
54 
55 int main(){
56     int cnt, count=0;
57     string s="";
58     s+=10;
59     cout<<s<<endl;
60     while(scanf("%d", &n) && n){
61         int u, v;
62         cnt=0;
63         scanf("%d%d", &num[cnt], &num[cnt+1]);
64         cnt+=2;
65         for(int i=2; i<=n; ++i){
66            scanf("%d%d", &u, &v);
67            num[cnt++]=v;
68         }    
69         n=cnt-1;
70         memset(dp, 0x3f, sizeof(dp));
71         memset(sign, 0, sizeof(sign));
72         for(int i=1; i<=n; ++i)
73            dp[i][i]=0;
74         for(int x=2; x<=n; ++x)
75           for(int i=1; i+x-1<=n; ++i){
76                int j=i+x-1;
77                for(int k=i; k<j; ++k){
78                    int tt=dp[i][k]+dp[k+1][j]+num[i-1]*num[k]*num[j];
79                    if(dp[i][j]>tt){
80                       dp[i][j]=tt;
81                       sign[i][j]=k;
82                    }
83                }
84           }
85     
86       cout<<"Case "<<++count<<": ";
87       traceBack();
88 
89      // cout<<"Case "<<++count<<": ";
90      // traceBackTmp(1, n);
91      // cout<<endl;
92     }
93     return 0;
94 }
复制代码

 










本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/3915841.html,如需转载请自行联系原作者
目录
相关文章
|
3月前
|
测试技术 PHP 开发者
PHP 数组查找:为什么 `isset()` 比 `in_array()` 快得多?
PHP 数组查找:为什么 `isset()` 比 `in_array()` 快得多?
|
7月前
|
人工智能 Java
Java 中数组Array和列表List的转换
本文介绍了数组与列表之间的相互转换方法,主要包括三部分:1)使用`Collections.addAll()`方法将数组转为列表,适用于引用类型,效率较高;2)通过`new ArrayList&lt;&gt;()`构造器结合`Arrays.asList()`实现类似功能;3)利用JDK8的`Stream`流式计算,支持基本数据类型数组的转换。此外,还详细讲解了列表转数组的方法,如借助`Stream`实现不同类型数组间的转换,并附带代码示例与执行结果,帮助读者深入理解两种数据结构的互转技巧。
363 1
Java 中数组Array和列表List的转换
|
7月前
|
JavaScript 前端开发 API
JavaScript中通过array.map()实现数据转换、创建派生数组、异步数据流处理、复杂API请求、DOM操作、搜索和过滤等,array.map()的使用详解(附实际应用代码)
array.map()可以用来数据转换、创建派生数组、应用函数、链式调用、异步数据流处理、复杂API请求梳理、提供DOM操作、用来搜索和过滤等,比for好用太多了,主要是写法简单,并且非常直观,并且能提升代码的可读性,也就提升了Long Term代码的可维护性。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
10月前
|
存储 Go 索引
go语言中的数组(Array)
go语言中的数组(Array)
197 67
|
7月前
|
移动开发 运维 供应链
通过array.some()实现权限检查、表单验证、库存管理、内容审查和数据处理;js数组元素检查的方法,some()的使用详解,array.some与array.every的区别(附实际应用代码)
array.some()可以用来权限检查、表单验证、库存管理、内容审查和数据处理等数据校验工作,核心在于利用其短路机制,速度更快,节约性能。 博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
7月前
|
供应链 JavaScript 前端开发
通过array.every()实现数据验证、权限检查和一致性检查;js数组元素检查的方法,every()的使用详解,array.some与array.every的区别(附实际应用代码)
array.every()可以用来数据验证、权限检查、一致性检查等数据校验工作,核心在于利用其短路机制,速度更快,节约性能。 博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
7月前
|
Web App开发 存储 前端开发
别再用双层遍历循环来做新旧数组对比,寻找新增元素了!使用array.includes和Set来提升代码可读性
这类问题的重点在于能不能突破基础思路,突破基础思路是从程序员入门变成中级甚至高级的第一步,如果所有需求都通过最基础的业务逻辑来做,是得不到成长的。 博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
7月前
|
数据采集 JavaScript 前端开发
JavaScript中通过array.filter()实现数组的数据筛选、数据清洗和链式调用,JS中数组过滤器的使用详解(附实际应用代码)
用array.filter()来实现数据筛选、数据清洗和链式调用,相对于for循环更加清晰,语义化强,能显著提升代码的可读性和可维护性。博客不应该只有代码和解决方案,重点应该在于给出解决方案的同时分享思维模式,只有思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
12月前
|
人工智能 前端开发 JavaScript
拿下奇怪的前端报错(一):报错信息是一个看不懂的数字数组Buffer(475) [Uint8Array],让AI大模型帮忙解析
本文介绍了前端开发中遇到的奇怪报错问题,特别是当错误信息不明确时的处理方法。作者分享了自己通过还原代码、试错等方式解决问题的经验,并以一个Vue3+TypeScript项目的构建失败为例,详细解析了如何从错误信息中定位问题,最终通过解读错误信息中的ASCII码找到了具体的错误文件。文章强调了基础知识的重要性,并鼓励读者遇到类似问题时不要慌张,耐心分析。
304 5