https://yukicoder.me/problems/no/771
前提知識
解法
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; }