SOMPO HD プログラミングコンテスト2021 F - Potion (600)
制約から全ポーションを使っても目標値は超えない
余りを使って計算したいのでいくつのポーションを使うかを全探索し最小値が答え
$ dp[i][j][k] でi番目まで見てj個使い、合計を使うポーションすうで割った余りがkの時の合計値の最大値とする
基本的に値が0の場合はその値を作れなかったということなので飛ばす
i番目が最初だった場合だけは特別で計算する
tを使う個数として$ dp[i][t][x \mod t] の中の最大値が条件を満たす最大の魔力
$ \frac{x - dp[i][t][x \mod t]}{t} が必要な時間
全てのパターンでの最小の必要な時間が答え
$ i番目まで見たときのDPの更新が$ O(N^2)で$ N個、使う個数も$ O(N)個探索する必要があるので全体で$ O(N^4)