福建漳州东山规划建设局网站,宁波建网站选哪家好一点,中国经济网官网,app软件开发制作公司电话题目链接#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;如果为’.则表示不需要使用。你的任务是安排十个…题目链接Pipeline Scheduling 题目描述 给定一张5×n(1≤n≤20)5\times n(1\le n\le20)5×n(1≤n≤20)的资源需求表第iii行第jjj列的值为’X’表示进程在jjj时刻需要使用使用资源iii如果为’.则表示不需要使用。你的任务是安排十个相同进程的启动时间使得所有进程完成的时间尽可能的早。在安排每个进程的开始时间你需要注意 一个进程一旦开始就必须要一直执行而不能停止任意一个资源必须进行互斥使用也就是任意时刻jjj需要保证对于1≤i≤51\le i\le51≤i≤5iii资源最多只被一个进程所使用。 你需要输出最早的完成时间。 例如输入为 对应的输出应该是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中的最小值如果nowStartTimerestProcessNum×minDelayTimen≥nowAnsnowStartTime restProcessNum \times minDelayTime n \ge nowAnsnowStartTimerestProcessNum×minDelayTimen≥nowAns那么我们直接进行剪枝即可即假设后续所有的进程都能最早开始但是依然不能早于当前记录的答案时进行减值。 代码
#include bits/stdc.hconst 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;
vectorint 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;
}
