当前位置: 首页 > news >正文

[NYOJ 536] 开心的mdd

开心的mdd

时间限制: 1000 ms  |  内存限制:65535 KB
难度: 3

描述
himdd有一天闲着无聊,随手拿了一本书,随手翻到一页,上面描述了一个神奇的问题,貌似是一个和矩阵有关的东西。

给出三个矩阵和其行列A1(10*100),A2(100*5),A3(5*50)。现在himdd要算出计算矩阵所要的乘法次数,他发现不同的计算次序,所要的乘法次数也不一样,

如:

(A1*A2)*A3 : 10*100*5+5*10*50=7500;

A1*(A2*A3) : 5*100*50+10*100*50 =75000;

他想知道计算矩阵所要的最少乘法次数是多少,很快一个解法就诞生了,有点小happy~~现在他想问问你是否也能找出一个解法呢?

注意:矩阵不可改变顺序。

 

输入
有多组测试数据(<=100),每组表述如下:
第一行,有一个整数n矩阵的个数(1<=n<=100)
接下来有n行
第i行有两整数,r,c表示第i个矩阵的行列;(1<=r,c<=100)


输出
输出计算矩阵所要的最少乘法次数。


样例输入
3
10 100
100 5
5 50

 

样例输出

7500

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define min _cpp_min
#define INF 0x7ffffff
#define N 110

int n;
int a[N];
int dp[N][N];                               //dp[i][j]表示pi*..*pj的最少次数

int main()
{
    int i,j,k,len;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i-1],&a[i]);
            dp[i][i]=0;
        }
        for(len=2;len<=n;len++)
        {
            for(i=1;i<=n-len+1;i++)
            {
                j=i+len-1;
                dp[i][j]=INF;
                for(k=i;k<j;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j]);
                }
            }
        }
        cout<<dp[1][n]<<endl;
    }
    return 0;
}
 

 

转载于:https://www.cnblogs.com/hate13/p/4109583.html

相关文章:

  • SQL死锁-阻塞
  • c++ mysql connector 学习汇总
  • 2014/11/21
  • Day2----subMeau
  • reaver使用相关
  • Linux Kernel Synchronization Mutual Exclusion、Linux Kernel Lock Mechanism Summarize
  • ASP.NET静态页生成
  • 清除浮动的方法有哪些?
  • C语言 要求用户录入5个数字,用函数来完成升序排序输出!
  • js词法分析2
  • [LeetCode] Merge Two Sorted Lists
  • telnet测试端口号
  • 已有打开的与此 Command 相关联的 DataReader,必须首先将它关闭。
  • DateTime.ToString格式化日期,使用DateDiff方法获取日期时间的间隔数
  • EasyMock的使用
  • __proto__ 和 prototype的关系
  • co.js - 让异步代码同步化
  • css的样式优先级
  • Git的一些常用操作
  • Lucene解析 - 基本概念
  • Octave 入门
  • Python 使用 Tornado 框架实现 WebHook 自动部署 Git 项目
  • Python十分钟制作属于你自己的个性logo
  • 从 Android Sample ApiDemos 中学习 android.animation API 的用法
  • 关于List、List?、ListObject的区别
  • 买一台 iPhone X,还是创建一家未来的独角兽?
  • 前端_面试
  • 三栏布局总结
  • 一些css基础学习笔记
  • 用jQuery怎么做到前后端分离
  • 大数据全解:定义、价值及挑战
  • ​queue --- 一个同步的队列类​
  • (C语言)输入一个序列,判断是否为奇偶交叉数
  • (python)数据结构---字典
  • (Repost) Getting Genode with TrustZone on the i.MX
  • (办公)springboot配置aop处理请求.
  • (二)什么是Vite——Vite 和 Webpack 区别(冷启动)
  • (紀錄)[ASP.NET MVC][jQuery]-2 純手工打造屬於自己的 jQuery GridView (含完整程式碼下載)...
  • (三)uboot源码分析
  • (十)T检验-第一部分
  • (已解决)什么是vue导航守卫
  • (转)ABI是什么
  • .net CHARTING图表控件下载地址
  • .NET CLR Hosting 简介
  • .NET DataGridView数据绑定说明
  • .net 按比例显示图片的缩略图
  • .Net 垃圾回收机制原理(二)
  • .NET 应用架构指导 V2 学习笔记(一) 软件架构的关键原则
  • .NET平台开源项目速览(15)文档数据库RavenDB-介绍与初体验
  • .NET中winform传递参数至Url并获得返回值或文件
  • .NET中使用Protobuffer 实现序列化和反序列化
  • /usr/local/nginx/logs/nginx.pid failed (2: No such file or directory)
  • @Mapper作用
  • @property @synthesize @dynamic 及相关属性作用探究
  • [ 英语 ] 马斯克抱水槽“入主”推特总部中那句 Let that sink in 到底是什么梗?