題意：給出5個工作單元，有10個完全相同的程序需要執(zhí)行，工作單元要避免沖突，問所有程序執(zhí)行完所需的時間最短是多少？

例：

7
X...XX.
.X.....
..X....
...X...
......X

7代表時間片，每個工作單元調用次數(shù)不固定，工作單元不能沖突，此數(shù)據(jù)最短時間為34。

分析：

這個只能是暴力求解，但是容易超時，我的想法就是每次枚舉它的偏移量，判斷是否沖突，加上剪枝。但是超時，就算是初始化所有可能偏移量加上預期剪枝還是超時，測試數(shù)據(jù)是真的強。

超時代碼如下：

#include<iostream> #include<string> #include<string.h> #include<queue> #include<vector> #include<list> #include<set> #include<sstream> #include<algorithm> #include<iomanip> using namespace std; const int maxn = 200 + 10; int mp[maxn],n,maxt=20000; int tp[maxn][20+5]; int ttemp[20 + 5]; int a[maxn]; int cnt = 0, diffarray[maxn]; bool isok(int k) {for (int i = 0; i < 5; i++) {if (a[i] & (a[i] >> k))return false;}return true; } void dfs(int layer, int diff) {if (layer == 10) {maxt = min(diff + n, maxt);return;}if (diff+(10-layer)*diffarray[0] >= maxt)return;//預期判斷for (int k = 0 ;k<cnt; k++) {//枚舉所有偏移量memset(ttemp, 0, sizeof(ttemp));int j = diff + diffarray[k];int ok = 1;for (int z = j; z < j + n; z++) {if (tp[z][mp[z - j]] == 1) {ok = 0;break;}}if (ok) {for (int z = j; z < j + n; z++) {tp[z][mp[z - j]] = 1;ttemp[z - j] = mp[z - j];}//memcpy(ttemp, mp, sizeof(mp));dfs(layer+1, j + 1);for (int i = 0; i < n; i++) {tp[j + i][ttemp[i]] = 0;}}} } int main() {char x;while (cin >> n && n) {int k = 1; maxt = 200000;memset(mp, 0, sizeof(mp));memset(tp, 0, sizeof(tp));memset(diffarray, 0, sizeof(diffarray));cnt = 0;for (int i = 0; i < 5; i++) {for (int j = 0; j < n; j++) {cin >> x;if (x == 'X') {mp[j] = i;tp[j][i] = 1;a[i] = 1 << j;//用二進制模擬}}}for (int i = 1; i <= n; i++) {if (isok(i))diffarray[cnt++] = i;//保存所有可能的偏移量}dfs(1, 1);cout << maxt-1<< endl;}return 0; }

看了大佬的二進制模擬，真是巧妙，想不到，我用數(shù)組一個一個判斷工作單元是否沖突，人家用二進制直接判斷程序之間的所有工作單元是否沖突。

二進制模擬：

#include <cstdio> #include <cstring> #include<iostream> #include <algorithm> using namespace std;const int maxn = 25; int n, a[5], dt[maxn], ans, cnt;bool ok(int *p, int k) {for (int i = 0; i < 5; ++i)if (a[i] & (p[i] >> k)) return false;return true; }void dfs(int *p, int d, int sum) {if (sum + dt[0] * (10 - d) >= ans) return;if (d == 10) { ans = min(ans, sum); return; }for (int i = 0; i < cnt; ++i) {if (ok(p, dt[i])) {//直接判斷當前程序的所有工作單元和已經(jīng)被占用的工作單元是否沖突int p2[5];for (int j = 0; j < 5; ++j)p2[j] = (p[j] >> dt[i]) | a[j];//時間片前進，所有單元后移，沒有沖突，加上新單元dfs(p2, d + 1, sum + dt[i]);}}return; }int main() {while (cin>>n&&n) {memset(a, 0, sizeof(a));memset(dt, 0, sizeof(dt));char x;for (int i = 0; i < 5; i++) {for (int j = 0; j < n; j++) {cin >> x;if (x == 'X')a[i] |= (1 << j);//存入位置量}}cnt = 0;for (int i = 1; i <= n; ++i)if (ok(a, i)) dt[cnt++] = i;//找到所有可能偏移量ans = 10 * n;dfs(a, 1, n);cout << ans << endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的UVA690 Pipeline Scheduling 流水线调度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。