しおり [yukicoder No.771]

https://yukicoder.me/problems/no/771

前提知識

• bitDP

解法

https://yukicoder.me/submissions/307901

制約からbitDP感がある。
その方向で考えると、以下のDPができる。
dp[msk][lst] := 今までmskの本が本棚に入っていて、最後の本がlstのときの醜さ
ここから、次の遷移先はO(N)ある。
次にnxtの本を入れるとき、しおり間距離は、B[lst]-A[lst]+A[nxt]となるので、それとの最大値を取り、
その最小値を更新していく。

int N, A[20], B[20];
int dp[1 << 18][18];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];
    rep(msk, 0, 1 << N) rep(lst, 0, N) dp[msk][lst] = inf;

    rep(i, 0, N) dp[1 << i][i] = 0;
    rep(msk, 0, 1 << N) rep(lst, 0, N) rep(nxt, 0, N) if(msk & (1 << lst)) if(!(msk & (1 << nxt))) {
        chmin(dp[msk + (1 << nxt)][nxt], max(dp[msk][lst],B[lst] - A[lst] + A[nxt]));
    }
    int ans = inf;
    rep(lst, 0, N) chmin(ans, dp[(1 << N) - 1][lst]);
    cout << ans << endl;
}