当前位置: 首页 > 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的使用
  • create-react-app项目添加less配置
  • HTTP 简介
  • Java知识点总结(JavaIO-打印流)
  • Netty源码解析1-Buffer
  • Promise初体验
  • React-flux杂记
  • Spring Boot MyBatis配置多种数据库
  • Spring Cloud中负载均衡器概览
  • Swift 中的尾递归和蹦床
  • Vue全家桶实现一个Web App
  • 干货 | 以太坊Mist负责人教你建立无服务器应用
  • 在Docker Swarm上部署Apache Storm:第1部分
  • 7行Python代码的人脸识别
  • Linux权限管理(week1_day5)--技术流ken
  • MPAndroidChart 教程:Y轴 YAxis
  • ​​​​​​​sokit v1.3抓手机应用socket数据包: Socket是传输控制层协议,WebSocket是应用层协议。
  • ​一文看懂数据清洗:缺失值、异常值和重复值的处理
  • # centos7下FFmpeg环境部署记录
  • #QT项目实战(天气预报)
  • #在线报价接单​再坚持一下 明天是真的周六.出现货 实单来谈
  • (2009.11版)《网络管理员考试 考前冲刺预测卷及考点解析》复习重点
  • (9)YOLO-Pose:使用对象关键点相似性损失增强多人姿态估计的增强版YOLO
  • (C语言)strcpy与strcpy详解,与模拟实现
  • (附源码)springboot 智能停车场系统 毕业设计065415
  • (附源码)springboot学生选课系统 毕业设计 612555
  • (四) Graphivz 颜色选择
  • (学习日记)2024.04.10:UCOSIII第三十八节:事件实验
  • (正则)提取页面里的img标签
  • (转)Android中使用ormlite实现持久化(一)--HelloOrmLite
  • (转)清华学霸演讲稿:永远不要说你已经尽力了
  • .libPaths()设置包加载目录
  • .NET 表达式计算:Expression Evaluator
  • .NET 应用启用与禁用自动生成绑定重定向 (bindingRedirect),解决不同版本 dll 的依赖问题
  • .NET/C# 获取一个正在运行的进程的命令行参数
  • .NET中winform传递参数至Url并获得返回值或文件
  • @RequestMapping处理请求异常
  • @WebServiceClient注解,wsdlLocation 可配置
  • @拔赤:Web前端开发十日谈
  • [AutoSAR系列] 1.3 AutoSar 架构
  • [BZOJ2850]巧克力王国