vijos 1243 生产产品 单调性优化动态规划

2024-04-03 21:48

本文主要是介绍vijos 1243 生产产品 单调性优化动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述 Description

在经过一段时间的经营后,dd_engi的OI商店不满足于从别的供货商那里购买产品放上货架,而要开始自己生产产品了!产品的生产需要M个步骤,每一个步骤都可以在N台机器中的任何一台完成,但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同,它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时间K。同时,为了保证安全和产品的质量,每台机器最多只能连续完成产品的L个步骤。也就是说,如果有一台机器连续完成了产品的L个步骤,下一个步骤就必须换一台机器来完成。现在,dd_engi的OI商店有史以来的第一个产品就要开始生产了,那么最短需要多长时间呢? 
某日Azuki.7对跃动说:这样的题目太简单,我们把题目的范围改一改 
对于菜鸟跃动来说,这是个很困难的问题,他希望你能帮他解决这个问题

 输入格式 Input Format

第一行有四个整数M, N, K, L 
下面的N行,每行有M个整数。第I+1行的第J个整数为T[I,J]。

输出格式 Output Format
输出只有一行,表示需要的最短时间。
样例输入 Sample Input

3 2 0 2
2 2 3
1 3 1


样例输出 Sample Output
4
时间限制 Time Limitation
1s
注释 Hint
对于50%的数据,N<=5,L<=4,M<=10000
对于100%的数据,N<=5, L<=50000,M<=100000

 

这道题是在看论文时看到的,于是到vijos那注册了一个账号来做做,谁知竟然做了一个下午,悲剧……

由于理论性的东西已经学过了,知道这是个dp+单调队列。可第一次编还是编了好久。

首先,很容易写出动态转移方程:f(i,j)=min( min( f(p,i) ) + sum(i,j) - sum(i,k) +val) ,i>k>i-l+1,m>p>0 && p!=i

由于m很小,小于6,所以,这个方程的主要优化在于寻找外层的min

而单调队列的方程为:f(x)= opt( cost[i] ) bound[x] <=i<x;

将动态转移方程化简得:f(i,j)=min( min( f(p,i) ) - sum(i,k) ) + sum(i,j)+val ,i>k>i-l+1,m>p>0 && p!=i

这样就可以用单调队列实现了。

 

View Code
  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<iostream>
  4 #include<string>
  5 #include<queue>
  6 #include<deque>
  7 #include<map>
  8 #include<cmath>
  9 #include<stack>
 10 #include<algorithm>
 11 #include<functional>
 12 using namespace std;
 13 const int N=6;
 14 const int L=50010;
 15 const int M=100010;
 16 typedef __int64 LL;
 17 struct TT{
 18     LL val;
 19     int num;
 20     TT(LL v,int n){val=v,num=n;};
 21 };
 22 deque<TT>que[N];
 23 LL sum[N][M];
 24 LL str[N][M];
 25 int l,n;
 26 LL kk;
 27 void init(){
 28     for(int i=0;i<n;i++){
 29         while(!que[i].empty()){
 30             que[i].pop_back();
 31         }
 32         que[i].push_back(TT(0,-1));
 33         str[i][0]=sum[i][0];
 34     }
 35 }
 36 void update(int k){
 37     int first=0,second=0,now;
 38     LL tmp;
 39     if(str[0][k]>str[1][k])first=1;
 40     else second=1;
 41     
 42     for(int i=2;i<n;i++){
 43         if(str[i][k]<=str[first][k]){
 44             second=first,first=i;
 45         }else{
 46             if(str[i][k]<str[second][k]){
 47                 second=i;
 48             }
 49         }
 50     }
 51 
 52     for(int i=0;i<n;i++){
 53         now=first;
 54         if(i==now){
 55             now=second;
 56         }
 57         tmp=str[now][k]-sum[i][k]+kk;
 58         while(!que[i].empty() &&que[i].front().num+l<=k)que[i].pop_front();
 59         while(!que[i].empty() && que[i].back().val>=tmp)que[i].pop_back();
 60         que[i].push_back(TT(tmp,k));
 61 
 62     }
 63     
 64 }
 65 int main()
 66 {
 67     int m,i,j;
 68     LL ans;
 69     while(~scanf("%d%d%d%d",&m,&n,&kk,&l)){
 70         for(i=0;i<n;i++){
 71             scanf("%I64d",&sum[i][0]);
 72             for(j=1;j<m;j++){
 73                 scanf("%I64d",&sum[i][j]);
 74                 sum[i][j]+=sum[i][j-1];
 75             }
 76         }
 77 
 78         
 79         if(n==1){
 80             printf("%I64d\n",sum[0][m-1]);
 81         }else{
 82             init();
 83     
 84             for(i=0;i<m;i++){
 85                 for(j=0;j<n;j++){
 86                     str[j][i]=que[j].front().val+sum[j][i];
 87                 }
 88                 update(i);
 89             }
 90             m--;
 91             ans=str[0][m];
 92             for(int i=1;i<n;i++){
 93                 if(ans>str[i][m])ans=str[i][m];
 94             }
 95             printf("%I64d\n",ans);
 96         }
 97     }
 98 
 99 
100     
101     return 0;
102 }
103 /*
104 3 2 2 1
105 1 2 3
106 1 2 3
107 */

 

 

 



 

这篇关于vijos 1243 生产产品 单调性优化动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/874067

相关文章

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

MySQL中慢SQL优化方法的完整指南

《MySQL中慢SQL优化方法的完整指南》当数据库响应时间超过500ms时,系统将面临三大灾难链式反应,所以本文将为大家介绍一下MySQL中慢SQL优化的常用方法,有需要的小伙伴可以了解下... 目录一、慢SQL的致命影响二、精准定位问题SQL1. 启用慢查询日志2. 诊断黄金三件套三、六大核心优化方案方案

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

使用国内镜像源优化pip install下载的方法步骤

《使用国内镜像源优化pipinstall下载的方法步骤》在Python开发中,pip是一个不可或缺的工具,用于安装和管理Python包,然而,由于默认的PyPI服务器位于国外,国内用户在安装依赖时可... 目录引言1. 为什么需要国内镜像源?2. 常用的国内镜像源3. 临时使用国内镜像源4. 永久配置国内镜

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4