流水线调度 Pipeline Scheduling
题意翻译
### 题目描述
你有一台有 $5$ 个工作单元的计算机,以及 $10$ 个完全相同的程序需要执行,每个程序需要用 $n\ (n \le 20)$ 个时间片来执行,程序的执行用一个 $5$ 行 $n$ 列的保留表表示,第 $i$ 行 $j$ 列为 $X$ 表示“当一个程序执行到第 $j$ 个时间片时需要工作单元 $i$ ”。一个工作单元不能同时被多个程序使用,因此需要知道安排这 $10$ 个程序的开始时间,使执行完所有程序所用的时间最短。
### 输入格式
**输入包含多组数据。**
每组数据共六行:\
第 $1$ 行,一个整数 $n$;\
接下来 $5$ 行,每行 $n$ 列,输入“.”或“ $X$”表示保留表,意义如题面所述。
输入以一个 $0$ 结束。
### 输出格式
每组数据一行,输出一个整数表示执行所有程序最小用时。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=631
[PDF](https://uva.onlinejudge.org/external/6/p690.pdf)
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA690/163b7ccd3d193a83d0c1f97ae29b2be7b657c64e.png)
输入输出格式
输入格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA690/72a8d2645924a6092613ac9470f636a46caffcf3.png)
输出格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA690/a009c4e2dacaa52b64d28443b956672c9d3cff74.png)
输入输出样例
输入样例 #1
7
X...XX.
.X.....
..X....
...X...
......X
0
输出样例 #1
34