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

UVa 690 Pipeline Scheduling 流水线调度 二进制表示状态 DFS 剪枝

题目链接:Pipeline Scheduling
题目描述:

给定一张5×n(1≤n≤20)5\times n(1\le n\le20)5×n(1n20)的资源需求表,第iii行第jjj列的值为’X’表示进程在jjj时刻需要使用使用资源iii,如果为’.'则表示不需要使用。你的任务是安排十个相同进程的启动时间,使得所有进程完成的时间尽可能的早。在安排每个进程的开始时间你需要注意:

  • 一个进程一旦开始就必须要一直执行,而不能停止;
  • 任意一个资源必须进行互斥使用,也就是任意时刻jjj需要保证对于1≤i≤51\le i\le51i5iii资源最多只被一个进程所使用。

你需要输出最早的完成时间。
例如输入为:
在这里插入图片描述
对应的输出应该是343434,对应的每个进程的执行情况如下表(图中的编号代表进程的编号):
在这里插入图片描述

题解:

本题不难想到的暴力方法是,枚举十个进程的开始时间,由于一共有十个进程每个进程开始的时间范围为:[0,n][0, n][0,n],所以时间复杂度为O(n10)O(n^{10})O(n10)
这样需要枚举的状态太多了,如何减少状态呢?在我们已知每个资源关于时间的需求情况实际上我们可以知道并不是[0,n][0, n][0,n]所有的开始时间都是可行的,我们能够确定出有限个可行的开始时间。我们设当前进程相对于上一个进程晚开始delayTimedelayTimedelayTime,那么此时当前的进程会在那些时刻占用那些资源是可以确定的,而只有当前进程占用的资源与上一个进程占用的资源不存在冲突的时候delayTimedelayTimedelayTime才是可行的,如果能够提前计算出所有的delayTimedelayTimedelayTime,那么最后进行枚举的时候复杂度就会大大减少。
如何快速判断一个delayTimedelayTimedelayTime是否可行?我们可以用二进制来保存每个资源与时间的关系,例如样例的输入我们可以用二进制表示为:
status[0]=0110001status[1]=0000010status[2]=0000100status[3]=0001000status[4]=1000000status[0] = 0110001\\ status[1] = 0000010\\ status[2] = 0000100\\ status[3] = 0001000\\ status[4] = 1000000status[0]=0110001status[1]=0000010status[2]=0000100status[3]=0001000status[4]=1000000
而当前进程相对于上一个进程延迟delayTimedelayTimedelayTime后开始,那么上一个进程在当前进程的各个资源占用会产生影响的部分实际上是status[i]>>delayTimestatus[i] >> delayTimestatus[i]>>delayTime(注意这里使用的二进制表示和图上是颠倒的,所以此处需要用右移表示时间的流逝,而如果不颠倒处理需要进行特定的位数判断比较麻烦),而当前进程的资源使用情况就是status[i]status[i]status[i],所以只要KaTeX parse error: Expected 'EOF', got '&' at position 11: status[i] &̲ (status[i] >>d…就代表资源iii不会发生冲突,只有五个资源都不发生冲突的delayTimedelayTimedelayTime才是可行的。
还有剪枝方法吗?实际上这样应该能够通过大部分数据,但是我们还有一个比较简单的剪枝,但是这个剪枝能够去除掉很多的状态。我们需要记录一个minDelayTimeminDelayTimeminDelayTime表示所有delayTimedelayTimedelayTime中的最小值,如果nowStartTime+restProcessNum×minDelayTime+n≥nowAnsnowStartTime + restProcessNum \times minDelayTime + n \ge nowAnsnowStartTime+restProcessNum×minDelayTime+nnowAns,那么我们直接进行剪枝即可(即假设后续所有的进程都能最早开始但是依然不能早于当前记录的答案时进行减值)。

代码:

#include <bits/stdc++.h>const int INF = 0x3f3f3f3f;
const int UNIT_NUM = 5;
const int PROCESS_NUM = 10;using namespace std;int ans, n, minDelayTime;
int status[UNIT_NUM];
string reservationTable;
vector<int> nextStep;void init()
{nextStep.resize(0);ans = INF;minDelayTime = -1;for (int delayTime = 1; delayTime <= n; delayTime++) {bool canStart = true;for (int unitID = 0; unitID < UNIT_NUM; unitID++) {if ((status[unitID] >> delayTime) & status[unitID]) {canStart = false;break;}}if (canStart) {if (minDelayTime == -1) { minDelayTime = delayTime; }nextStep.push_back(delayTime);}}
}void dfs(int nowDepth, int nowStartTime, int s0, int s1, int s2, int s3, int s4) {if (nowDepth == PROCESS_NUM - 1) { // 这里等于PROCESS_NUM - 1是因为0号进程已经安排到0时刻开始,后续安排的是1-9号进程ans = min(ans, nowStartTime + n);return ;}if (nowStartTime + (9 - nowDepth) * minDelayTime + n >= ans) { return; }for (int delayTime : nextStep) {int ns0 = s0 >> delayTime, ns1 = s1 >> delayTime, ns2 = s2 >> delayTime, ns3 = s3 >> delayTime, ns4 = s4 >> delayTime;if ((ns0 & status[0]) || (ns1 & status[1]) || (ns2 & status[2]) || (ns3 & status[3]) || (ns4 & status[4])) {continue; }dfs(nowDepth + 1, nowStartTime + delayTime, ns0 | status[0], ns1 | status[1], ns2 | status[2], ns3 | status[3], ns4 | status[4]);}
}int main()
{ios::sync_with_stdio(false);while (cin >> n && n != 0) {for (int i = 0; i < UNIT_NUM; i++) {cin >> reservationTable;status[i] = 0;for (int j = 0; j < n; j++) {if (reservationTable[j] == 'X') {status[i] |= 1 << j;}}}init();dfs(0, 0, status[0], status[1], status[2], status[3], status[4]);cout << ans << endl;}return 0;
}

相关文章:

UVa 690 Pipeline Scheduling 流水线调度 二进制表示状态 DFS 剪枝

题目链接&#xff1a;Pipeline Scheduling 题目描述&#xff1a; 给定一张5n(1≤n≤20)5\times n(1\le n\le20)5n(1≤n≤20)的资源需求表&#xff0c;第iii行第jjj列的值为’X’表示进程在jjj时刻需要使用使用资源iii&#xff0c;如果为’.则表示不需要使用。你的任务是安排十个…...

【ArcGIS Pro二次开发】(6):工程(Project)的基本操作

在ArcGIS Pro中我们对工程的基本操作一般包括打开、新建、保存等。下面演示在二次开发中如何用代码进行以上操作。 新建一个项目&#xff0c;命名为【ProjectManager】&#xff0c;添加8个按钮&#xff0c;命名为【CreateEmptyProject、CreateProjectByDefault、OpenExProjest…...

Qt OpenGL(四十)——Qt OpenGL 核心模式-雷达扫描效果

提示:本系列文章的索引目录在下面文章的链接里(点击下面可以跳转查看): Qt OpenGL 核心模式版本文章目录 Qt OpenGL(四十)——Qt OpenGL 核心模式-雷达扫描效果 一、场景 上一篇文章介绍了在雷达坐标系中绘制飞行的飞机,其实雷达坐标系应该还有一个效果,就是扫描的效…...

群智能优化算法求解标准测试函数F1~F23之种群动态分布图(视频)

群智能优化算法求解标准测试函数F1的种群动态分布图群智能优化算法求解标准测试函数F2的种群动态分布图群智能优化算法求解标准测试函数F3的种群动态分布图群智能优化算法求解标准测试函数F4的种群动态分布图群智能优化算法求解标准测试函数F5的种群动态分布图群智能优化算法求…...

vue-axios封装与使用

一、简介 Axios 是一个基于 promise 网络请求库&#xff0c;作用于node.js 和浏览器中。 这是一个使用率很高的前端网络请求库&#xff0c;几乎所有的前端项目都会使用&#xff0c;本文主要介绍的是如何在vue项目中使用axios&#xff0c;并对其进行全面的封装。 注意&#x…...

重要节点排序方法

文章目录研究背景提前约定基于节点近邻的排序方法度中心性&#xff08;degree centrality, DC&#xff09;半局部中心性&#xff08;semilocal centrality, SLC&#xff09;k-壳分解法基于路径排序的方法离心中心性 (Eccentricity, ECC)接近中心性 (closeness centrality, CC)K…...

【2.20】动态规划 +项目 + 存储引擎

01背包问题 现有一容量为w的背包&#xff0c;有3个物品&#xff0c;每个物品重量不同&#xff0c;价值不同&#xff0c;问&#xff0c;怎样装才能价值最大化&#xff1f; 明确dp数组含义和下标含义&#xff1a;dp[j]表示当前背包的最大价值。j表示背包容量。递推公式&#xf…...

触摸屏单个按键远程控制led

一、硬件 arduino2块 淘晶驰串口屏7寸增强型带外壳1块,不支持视频音频 nRF24L0模块2块 扩展板2块 跳线若干 面包板1块 led灯1个 电阻二极管若干 下载线两个 usb转串口1个 二、实验内容 一个arduino作为触摸屏的控制器,接收触摸屏双向开关的信号,同时通过nRF24L01发送“open”…...

JVM12 class文件

1. Class 文件结构 1.1. Class 字节码文件结构 类型名称说明长度数量魔数u4magic魔数,识别Class文件格式4个字节1版本号u2minor_version副版本号(小版本)2个字节1u2major_version主版本号(大版本)2个字节1常量池集合u2constant_pool_count常量池计数器2个字节1cp_infoconstan…...

等保三级认证基本要求

一、什么是等保测评&#xff1f; 企业单位委托经公安部认证的具有资质的测评机构&#xff0c;按照管理规范和技术标准&#xff0c;对相应的测评对象&#xff08;信息系统&#xff09;的状况进行测评。 1、安全技术测评&#xff1a;包括物理安全、网络安全、主机系统安全、应用安…...

Python 基本数据类型(一)

1. 整型 整型即整数&#xff0c;用 int 表示&#xff0c;在 Python3 中整型没有长度限制。 1.1 内置函数 1. int&#xff08;num, baseNone&#xff09; int( ) 函数用于将字符串转换为整型&#xff0c;默认转换为十进制。 >>> int(123) 123 >>> int(123, …...

win10 环境变量及其作用大全

------------------------------------------------------系统变量------------------------------------------------------ ComSpec: C:\WINDOWS\system32\cmd.exe command specification 解释&#xff1a; ComSpec是Windows操作系统中的一个环境变量&#xff0c;它表示Windo…...

@Valid与@Validated的区别

1.介绍 说明&#xff1a; 其实Valid 与 Validated都是做数据校验的&#xff0c;只不过注解位置与用法有点不同。 不同点&#xff1a; &#xff08;1&#xff09; Valid是使用Hibernate validation的时候使用。Validated是只用Spring Validator校验机制使用。 &#xff08;2&…...

【LeetCode】剑指 Offer 09. 用两个栈实现队列 p68 -- Java Version

题目链接&#xff1a;https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/ 1. 题目介绍&#xff08;09. 用两个栈实现队列&#xff09; 用两个栈实现一个队列。队列的声明如下&#xff0c;请实现它的两个函数 appendTail 和 deleteHead &#xff0c;分别…...

Java并发编程面试题——JUC专题

文章目录一、AQS高频问题1.1 AQS是什么&#xff1f;1.2 唤醒线程时&#xff0c;AQS为什么从后往前遍历&#xff1f;1.3 AQS为什么用双向链表&#xff0c;&#xff08;为啥不用单向链表&#xff09;&#xff1f;1.4 AQS为什么要有一个虚拟的head节点1.5 ReentrantLock的底层实现…...

CAS概述

目录一、CAS与原子类1.1 CAS1.2 乐观锁与悲观锁1.3 原子操作类二、 synchronized优化2.1 轻量级锁2.2 轻量级锁-无竞争2.3 轻量级锁-锁膨胀2.4 重量级锁-自旋2.5 偏向锁2.6 synchronized-其他优化一、CAS与原子类 1.1 CAS CAS&#xff08;一种不断尝试&#xff09;即Compare …...

Ansys Zemax / SPEOS | 光源文件转换器

本文解释了如何在 SPEOS 与 Zemax 之间转换二进制光源文件。 下载 联系工作人员获取附件 简介 在本文中&#xff0c;为用户提供了一组Python代码&#xff0c;用于在Zemax和SPEOS之间转换源文件。 有些光源&#xff0c;如 .IES 文件&#xff0c;可在 SPEOS 和 Zemax 中进行…...

PRML笔记2-关于回归参数w的先验的理解

接上篇&#xff0c;现在考虑给w\boldsymbol{w}w加入先验&#xff0c;考虑最简单的假设&#xff0c;也就是w\boldsymbol{w}w服从均值为0&#xff0c;协方差矩阵为α−1I\alpha^{-1}\boldsymbol{I}α−1I的高斯分布。 p(w∣α)N(w∣0,α−1I)(α2π)(M1)/2exp⁡{−α2wTw}\begin{…...

Selenium原理

我们使用Selenium实现自动化测试&#xff0c;主要需要3个东西1.测试脚本&#xff0c;可以是python&#xff0c;java编写的脚本程序&#xff08;也可以叫做client端&#xff09;2.浏览器驱动, 这个驱动是根据不同的浏览器开发的&#xff0c;不同的浏览器使用不同的webdriver驱动…...

Disconf、Apollo和Nacos分布式配置框架差异对比

差异对比表格&#xff1a; 功能点DisconfApolloNacos依赖高可用框架完全依赖于Zookeeper来实现监听拉取&#xff0c;向外提供了HTTP拉取数据接口依赖于Eureka实现内部服务发现注册&#xff0c;提供HTTP接口给Client SDK拉取监听数据内部自研实现框架高可用CAP理论偏重点Zookee…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...