2014JOI予選6 小籠包 解説

問題リンク

解説

bit DP くらいしか解けそうな方法がなくて困るが、制約を眺めると $D_i\leq 7$ になっている。つまり、一定以上に離れた位置にある小籠包を食べる順番は美味しさの総和に関係ない。

次のような DP をする。

$dp[i][j]=i$ 番目の小籠包を食べる相対的な位置を次に決めて、それより前 $7$ 個の食べた順番が $j$ であるときの、ここまでで確保した美味しさの総和の最大値

美味しさは自分より前の小籠包に対してだけ計算して加算することにすれば、それより前の小籠包と次に決める小籠包は関係がないので、相対位置さえ決めればよく、この DP は正しい答えを導く。 こうすると、計算量が $O(N\max(D+1)!)$ になって、この問題が解ける。

なお、$j$ を非負整数にエンコードするのは、2007JOI春合宿3-1 のようにすればよい。