http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2427
全探索といえばこの問題だよね。
最初を除いたどの馬車も最小値をとりうる場合、次のうち二つの条件のうちどちらかを満たします。
1.終点or少し広いところで交わるほかの馬車が存在する。
2.1分前に出発した馬車が存在する。
なので最初の馬車から始めて、再帰的に全探索を行います。
ある時点ですでに見た馬車の集合Uに対して、Uに属さない馬車vを1つ選び、
Uに属する馬車と1or2の条件を満たすようにします。そしてUに属するほかの馬車とも矛盾が生じないか確認して、Uにvを追加します。これを繰り返せば馬車たちの出発時刻として成立し、最小値をとりうるするものをすべて列挙できます。
オーダーはよくわからないですがAOJで0.00sなので高速です。
ll dist; int N, M; ll S[10], D[10]; ll ans; vpl check(int v, const vl& b, vpl cross) { ll prev = 0; rep(i, 1, N) { if(b[i] == -1) continue; if(prev >= b[i]) return vpl(); prev = b[i]; } //cross rep(i, 0, N) { if(i == v || b[i] == -1) continue; ll s1 = S[v], s2 = S[i]; ll b1 = b[v], b2 = b[i]; if(v < i) { //b1 < b2 if(s1 - s2 > 0 && b2 - b1 < dist * (s1 - s2)) { if((b2 - b1) % (s1 - s2) != 0) return vpl(); ll d = (b2 - b1) / (s1 - s2); ll t = (s1 * b2 - s2 * b1) / (s1 - s2); //debug("check", b, d, res); bool ok = false; rep(j, 0, M) { if(d == D[j]) { if(count(all(cross), pl(t, d))) return vpl(); else { cross.pb(pl(t, d)); ok = true; break; } } } if(!ok) return vpl(); } } else { //b1 > b2 if(s2 - s1 > 0 && b1 - b2 < dist * (s2 - s1)) { if((b1 - b2) % (s2 - s1) != 0) return vpl(); ll d = (b1 - b2) / (s2 - s1); ll t = (s2 * b1 - s1 * b2) / (s2 - s1); //debug("check", b, d, res); bool ok = false; rep(j, 0, M) { if(d == D[j]) { if(count(all(cross), pl(t, d))) return vpl(); else { cross.pb(pl(t, d)); ok = true; break; } } } if(!ok) return vpl(); } } } return cross; } void loop(vl b, vpl cross) { //b = {0, -1, -1, -1, -1} beginning bool found = false; //debug(b, cross); rep(v, 0, N) { if(b[v] == -1) { rep(j, 0, N) { if(b[j] == -1) continue; //start if(j + 1 == v) { b[v] = b[j] + 1; vpl newcross = check(v, b, cross); if(!newcross.empty()) loop(b, newcross); b[v] = -1; } //cross rep(k, 0, M) { ll t = D[k] * S[j] + b[j]; ll tmp = t - D[k] * S[v]; if(tmp > 0) { b[v] = tmp; vpl newcross = check(v, b, cross); if(!newcross.empty()) loop(b, newcross); b[v] = -1; } } //end ll t = dist * S[j] + b[j]; ll tmp = t - dist * S[v]; if(tmp > 0) { b[v] = tmp; vpl newcross = check(v, b, cross); if(!newcross.empty()) loop(b, newcross); b[v] = -1; } } found = true; } } if(!found) { ll tmp = 0; rep(i, 0, N) MAX(tmp, dist * S[i] + b[i]); MIN(ans, tmp); } } void solve() { cin >> dist; cin >> N; rep(i, 0, N) cin >> S[i]; cin >> M; rep(i, 0, M) cin >> D[i]; ans = linf; vl vec(N, -1); vec[0] = 0; loop(vec, vpl(1, pl(-1, -1))); cout << ans << "\n"; }
実践的プログラミング結構エグイね。