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

n-knuu's logs

憧れ駆動。だいたい競プロ

九州大学プログラミングコンテスト2014 F. 設備移転

DP AtCoder

解法

DP。dp[i][j][k] := (建物iまでのうち、建物j個を移動させて、時間kかかったときの場合の数)とすると、
dp[i+1][j][k] += dp[i][j][k] (建物iを移動しない場合)
dp[i+1][j+D[i]][k+1] += dp[i][j][k] (建物iを移動させる場合、ただし j+D[i] <= T かつ k < N)
この漸化式を0 <= i < N, 0 <= j <= N, 0 <= k <= T で更新しく。答えはsum(dp[N][i][j], M <= i <= N かつ 0 <= j <= T)となる。

計算量

O(N^2 T)

コード

以下のコードではメモリ節約のために、更新用の配列 _dp を用意して、そこに更新している

感想

素直なDPだったけど、k+D[i]とするところをk+D[k]としていてout-of-boundsになっていた(どうせDPのどこかでout-of-boundsしているのだろうという先入観があって、ずっとそこを探していた)