JOI2015春合宿2-2 Keys 解説

問題リンク

解説

制約を見ると，時系列順に DP をしてやれば解けそうだが，ある社員が鍵を持っているかどうかの影響は，出た直後と戻る直前両方の時間に対して発生するので，時系列順に見るのは得策ではない．

ある社員が鍵を持っていないとき，出た直後の区間と戻る直前の区間では鍵を開けておかないといけない．逆に，これさえ満たしていれば残りの区間は全て鍵を閉められる． この区間がかぶるのは，ある社員の出発とある社員の到着がこの順で隣接して並ぶ場合のみである．よって，このように影響をもつ区間を共有する社員を列状にそれぞれ並べれば，これらの社員のグループを分けて考えられる．

これらの列のなかでは，何人が鍵を持つとき最小で何分ドアを開ける必要があるかを，時系列順の DP で求められる． すべての列についてこれらを計算すると，これらの情報が集約できるので，これらをまた DP で統合すれば答えが出る．

これらの DP では，

• $dp[i][j][k] = i$ 番目の社員まで見て，$j$ 人の社員が鍵を持ち，前の社員が鍵を持っていたかを $k$ で示すときの鍵を開ける時間の最小値
• $dp[i][j] = i$ 番目の列まで見て，$j$ 人の社員が鍵を持っているときの，鍵を帰る時間の最小値

としてやればよい． 時間計算量は $O(N^2)$ になる．