読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 250 Fastest Route

ICPC bitDP

ICPCを埋め始めましたよっと。

問題

このゲームには1番から N 番までの N 個のステージがあり,任意の順に攻略することができる. また,1から N まで番号付けられた装備があり,それらの装備を使用することでステージの攻略時間を短縮することができる. ゲームを始めた段階では装備は一つも持っていないが, i 番のステージを攻略すると i 番の装備を入手することができ,一度入手した後は何度でも使用できる. 装備は一ステージで一種類だけしか使用することができないが,異なるステージで同じ装備を使用することはできる.

このとき、すべてのステージをクリアするまでにかかる最小の時間を求めよ。

制約

ステージ数:  1 \leq N \leq 16

各装備を使ったときにかかる時間  1 \leq t_{ij} \leq 10^6

解法

bitDP。「どのステージを既に訪れたか」をbitで管理する。この解法に至る理由は次の2つ。

  • 制約のNが小さいこと (O(2N)でも十分通る)
  • 新たなステージ j を訪れるとき、そのステージをクリアするときに使える t の最小値はそれまでにどのステージを訪れたかにのみ依存し、それまでに訪れたステージの順番には依存しないこと

bitDPについては↓のスライドが参考になります。

www.slideshare.net

const int MAX_N = 16;
const int inf = 1e8;

int dp[1<<MAX_N];

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int N;
    while (cin >> N && N) {
        vector<vi> t(N, vi(N + 1));
        rep(i, N) rep(j, N + 1) cin >> t[i][j];

        rep(i, 1<<N) dp[i] = inf;
        dp[0] = 0;

        // bitDP
        // i: state(1 = visited stage)
        rep(i, 1<<N) {
            // if this state is not searched, then skip
            if (dp[i] == inf) continue;
            // j: nxt stage
            rep(j, N) {
                // if j has already been visited in state i, then skip
                if ((i>>j) & 1) continue;
                // search for minimum available t[j][?]
                int mint = t[j][0];
                rep(k, N) {
                    // if k is already visited in state i, then we can use item k
                    if ((i >> k) & 1) mint = min(mint, t[j][k + 1]);
                }
                dp[i | (1<<j)] = min(dp[i | (1<<j)], dp[i] + mint);
            }
        }

        cout << dp[(1<<N) - 1] << endl;
    }
    
}

ちょっとずつDPができるようになってきた。