アルゴリズムのお勉強 [Kotamanegi Online Judge No.70]

https://kotamanegi.com/Problems/view/index.php?page=70

前提知識

• bitDP

考察過程

1. N≦16の時点でbitDP感がある
2. 最短時間を聞かれてるのでbitDPで最小値のDPを考えると答えられる

解法

https://kotamanegi.com/Submission/view/index.php?SubmissionID=1622

bitDPで解く。
dp[msk] := mskのアルゴリズムを理解しているときにかかった最短時間
mskからmsk+(1<

int N, T[16], A[16][16], dp[1<<16];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> T[i];
    rep(i, 0, N) rep(j, 0, N) cin >> A[i][j];

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

    rep(msk, 0, 1 << N) rep(i, 0, N) if (!(msk & (1 << i))) {
        int t = T[i];
        rep(j, 0, N) if (msk & (1 << j)) t -= A[j][i];
        chmin(dp[msk + (1 << i)], dp[msk] + t);
    }
    cout << dp[(1 << N) - 1] << endl;
}