1204 - Pipeline Scheduling

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1204

問題

パイプラインの問題。パイプラインを知っていると理解しやすい。
あるタスクにおいて、各クロックで使用されるユニットのテーブルが与えられるので
conflictを起こさないように１０回タスクを実行するときの最短クロック数を求めよ。

解法

DFSで解いた。
計算量的に心配したがかなり余裕で出来た。

まず、１つのタスクを実行したとき、そのあとのクロックで実行できるか実行できないかを調べることができる。
n<=20ということなので、配列を使わずビットを使ってみた。
実装の都合上１ビット目は必ず0で、iクロック後に実行できるなら(i+1)ビット目が0、実行できないなら1というふうにした。

後は再帰により、実行できるところで取り敢えず実行してみて答えを見つける。
タスクを実行するときは、待った分だけビットを右シフトすればうまくいく。

ソース

int n;
int dame;

int rec(int S, int num) {                // iクロック後でタスクを始められなければ(i+1)ビット目が１
  if (num == 10) return n;
  int res = INF;
  for (int i=1;i<n;++i) {
    if (!(S >> i & 1)) {
      int tmp = S >> i;
      tmp |= dame;
      res = min(res, rec(tmp, num+1) + i);
    }
  }
  return res;
}

int main() {
  while(cin>>n,n) {
    int table[n];
    REP(i,5) {
      REP(j,n) {
        char c;
        cin >> c;
        if (c == 'X')
          table[j] = i; 
      }
    }
    dame = 0;
    for (int i=1; i<n; ++i)
      REP(j, i)
        if (table[i] == table[j])
          dame |= 1 << i-j;
    cout << rec(dame,1) << endl;
  }
}