流水线调度 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