九州大学プログラミングコンテスト2014 F. 設備移転
解法
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しているのだろうという先入観があって、ずっとそこを探していた)
