ABC017 D - サプリメント - ツバサの備忘録

解法

$dp[i] = i$ 番目までのサプリメントを飲む方法数
とします。
$i$ 番目のサプリメントを飲むときは、
$i$ 番目のみを1日で飲む
$i-1$ 番目と $i$ 番目の2つを1日で飲む
$i-2$ 番目から $i$ 番目の3つを1日で飲む
というように、同時に飲むこともできます。
しかし、 $i-k$ 番目から $i$ 番目の $k+1$ 個を1日で飲むには条件があり、
$i-k$ 番目から $i$ 番目まではすべて違う種類である必要があります。
ということで、
$dp[i] = \sum dp[i-k]$
となります。 $memo[i] = i$ 番目と同日に食べることができない $i$ 未満のサプリメントの番号の最大値
とすると、これが $k$ の最小値-1となり、これは $O(N)$ で準備することができます。
あとは、上の式をもとにして答えを求めるだけなのですが、このまま愚直に書くと部分点しかとれません。
$dp[i]$ を求める際に足す値は、区間になっているので、 $dp[x]$ についての累積和を同時に求めていけば、うまく $O(1)$ でdpの更新を行うことができ、これで答えが求まります。