Problem 1204 : Pipeline Scheduling

問題概要

CPUには5つの処理部分があり、1クロックごとに別の処理ができる。
与えられた長さnクロックの処理が、それぞれのクロックに使うCPUの部分のテーブルが与えられたとき、この処理を10回行うのに必要な最小のクロックを求めよ。

解法

クロック0で処理をしたときに、先の1〜nクロックに処理ができるかはあらかじめ判定しておくことができる。
処理が次のクロックにできるかどうかは、最後のnクロックの状態のみに依存するので、
そこ（処理が入れるかどうか）をビットで多重化してDijkstraすればよい。

ソースコード

int n,ng;
char in[4][21];

int main(){
	while(scanf("%d",&n),n){
		rep(i,5)scanf("%s",in[i]);
		ng=0;
		for(int i=0;i<=n;i++)rep(j,5)rep(k,n-i)
		if(in[j][i+k]=='X'&&in[j][k]=='X')ng|=1<<i;
		
		set<pair<int,int> > S;
		priority_queue<pair<int,pair<int,int> > > Q;
		Q.push(mp(-n,mp(1,ng)));
		while(!Q.empty()){
			int cc=Q.top().first,cnt=Q.top().second.first;
			int bit=Q.top().second.second; Q.pop();
			if(S.count(mp(cnt,bit)))continue; S.insert(mp(cnt,bit));
			if(cnt==10){
				 printf("%d\n",-cc); break;
			}
			for(int i=1;i<=n;i++)if(!(bit&1<<i))
			if(!S.count(mp(cnt+1,bit>>i|ng)))Q.push(mp(cc-i,mp(cnt+1,bit>>i|ng)));
		}
	}
	return 0;
}