Google Code Jam 2008 Qualification Round : A. Saving the Universe

GCJ2008は参加していないので練習。
http://code.google.com/codejam/contest/32013/dashboard#s=p0

検索エンジンリストと、そのあとに単語リストが与えられる。
単語リストの単語を順に検索する際、単語と同じ検索エンジンで検索してはいけない。
最少何回検索エンジンを切り替えるかを答える。

今回はDPで解いてみた。

int S,Q;
char str[101][300];
int q[1001];
int s[101],t[101];

void solve(int _loop) {
	int i,j,k,result,res,l;
	double br,tb1,tb2,start,end;
	char line[200];
	
	gets(line);
	sscanf(line,"%d",&S);
	FOR(i,S) gets(str[i]);
	
	gets(line);
	sscanf(line,"%d",&Q);
	FOR(i,Q) {
		gets(line);
		FOR(j,S) if(strcmp(str[j],line)==0) q[i]=j;
	}
	
	ZERO(t);
	FOR(i,Q) {
		memcpy(s,t,sizeof(s));
		FOR(j,S) {
			t[j]=99999;
			if(q[i]==j) continue;
			FOR(k,S) {
				if(k==j && t[j]>s[k]) t[j]=s[k];
				if(k!=j && t[j]>s[k]+1) t[j]=s[k]+1;
			}
			
		}
	}
	
	result=99999;
	FOR(i,S) result=min(result,t[i]);
	
	_PE("Case #%d: %d\n",_loop,result);
}

まとめ

予選１問目でDPなんか出すかな…？
現在位置からもっとも多くの単語を検索できる検索エンジンを探す、というのを貪欲に探せばそれでよかったのかも…。