AOJ2427 -- ほそながいところ

問題文: hosonagaitokoro | Aizu Online Judge

こういう系 (適切な方針を選ぶと非常に楽になる系) は結構好きです。以下白文字。

馬車 u が馬車 v (u > v) を抜かす場所 (あるいは抜かさない) を全探索すると、各馬車の出発時刻 x[u] に不等式制約が立つので牛をやる。ただし、同時に同じ場所で追い抜きができないので、ある馬車が同じ場所で 2 回以上追い抜きインシデントに遭遇するのは NG とする。O((n(n-1)/2)^(m+1) * n^3)

という方針でやると全然混乱せず実装も楽に一発 AC 出来てよかった。ソースは続き。

ソースコード(テンプレ略)

Int dist, N, S[8], M, D[8], A[8][8], C[8][8], P[8][8], Q[8], res;

void search(int u, int v) {
  if (u == N) {
    for (int i = 0; i < N; ++i) {
      Q[i] = INFLL;
      for (int j = 0; j < N; ++j) {
        P[i][j] = INFLL;
      }
    }
    for (int i = 1; i < N; ++i) {
      chmin(P[i][i - 1], -1LL);
      for (int j = 0; j < i; ++j) {
        if (A[i][j] == M) {
          chmin(P[i][j], dist * (S[i] - S[j]));
        } else {
          chmin(P[j][i], D[A[i][j]] * (S[j] - S[i]));
          chmin(P[i][j], D[A[i][j]] * (S[i] - S[j]));
        }
      }
    }
    Q[N - 1] = 0;
    for (int i = 0; i <= N * (N - 1); ++i) {
      bool cont = false;
      for (int j = 0; j < N; ++j) {
        for (int k = 0; k < N; ++k) {
          if (P[j][k] < INFLL && Q[j] + P[j][k] < Q[k]) {
            cont = true;
            Q[k] = Q[j] + P[j][k];
          }
        }
      }
      if (i == N * (N - 1) && cont) {
        return;
      }
    }
    Int t = 0;
    for (int i = 0; i < N; ++i) {
      chmax(t, (Q[i] - Q[0]) + dist * S[i]);
    }
    chmin(res, t);
  } else if (u == v) {
    search(u + 1, 0);
  } else {
    for (int i = 0; i <= M; ++i) {
      A[u][v] = i;
      ++C[u][i]; ++C[v][i];
      if (i == M || max(C[u][i], C[v][i]) <= 1) {
        search(u, v + 1);
      }
      --C[u][i]; --C[v][i];
    }
  }
}

int main() {
  while (~scanf("%lld", &dist)) {
    N = in();
    for (int i = 0; i < N; ++i) {
      S[i] = in();
    }

    M = in();
    for (int i = 0; i < M; ++i) {
      D[i] = in();
    }

    if (N == 1) {
      printf("%lld\n", S[0] * dist);
    } else {
      res = INFLL;
      memset(C, 0, sizeof(C));
      search(1, 0);
      printf("%lld\n", res);
    }
  }

  return 0;
}