UVA-690 流水线调度 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

一开始我看题目，疑惑为什么要用一张二维表，来表示程序执行的步骤，如果一个时钟周期只有一个单元在执行，完全可以用一个一维数组表示。

于是我按照这个结构做完，发现一直wrong。看udebug的数据发现：部分例子中，同一周期内可能执行多个单元。而有些周期内，可能任何一个单元都不执行。因此必须按照二位数组表示。极端情况下，所有周期的所有单元都不执行。例如：

4
....
....
....
....
....
0

此时所有程序可以同一时间执行，耗时为n。

题目总体来说不难，走到每一个程序时，循环尝试间隔任意步骤出发，看看最短时间为多少。第一个程序和第二个程序执行的间隔，可以认为是每个程序执行的最小间隔。通过这个间隔进行判断来剪枝。

AC代码

#include <stdio.h>
#include <string.h>
#define MAXN 21
#define STEP_NUM 5
#define TASK_NUM 10int n;
int program[MAXN][STEP_NUM];
int minLen, minInterval;
int steps[TASK_NUM];void init()
{memset(program, 0, sizeof(program));memset(steps, 0, sizeof(steps));minLen = TASK_NUM * n;minInterval = -1;
}// 判断当前有没有冲突
bool test(int s, int a)
{int i, j, k;int pos;// 对第s+1个执行循环步骤for (i = 0; i < n; ++i){// 当前位置pos = steps[s] + a + i;// 对前面已经执行过的步骤判断是否与当前执行冲突for (j = s; j >= 0; --j){if (steps[j] + n <= pos){if (j == s)return true;break;}for (k = 0; k < STEP_NUM; ++k){if (program[i][k] != 0 && program[pos - steps[j]][k] == program[i][k])return false;}}}return true;
}void compute(int s)
{if (s == TASK_NUM - 1){if (steps[s] + n < minLen)minLen = steps[s] + n;return;}int i, j;for (i = 0; i <= n; ++i){if (steps[s] + i + n + ((TASK_NUM - s - 2) * (minInterval == -1 ? 0 : minInterval)) >= minLen)return;if (!test(s, i))continue;if (s == 0 && minInterval == -1)minInterval = i;steps[s + 1] = steps[s] + i;compute(s + 1);}
}int main()
{int i, j, k;char c;while (scanf("%d", &n) == 1 && n > 0){init();for (i = 0; i < STEP_NUM; ++i){getchar();for (j = 0; j < n; ++j){c = getchar();if (c == 'X')program[j][i] = 1;}}steps[0] = 0;compute(0);printf("%d\n", minLen);}return 0;
}