ABC 162 F - Select Half

• 問題
• AC

前の整数を取ったら、次の整数は取れないし、前の整数を取らなかったらだいたい次の整数を取る必要があることに注目してDPする。

後者の場合は必ずしも取らないといけないわけではなく、何回かはパスする必要がある。$N$が偶数の場合はちょうど1回パスするべきで、$N$が奇数の場合はちょうど2回パスするべきである。したがって

$\operatorname{dp}[x][y][z] :=$ $a_1, ..., a_x$まで見て、整数$a_x$を取り$(y=1)$/取らず$(y=0)$、今までにパスした回数が$z$である場合の最大値

としてDPすればよい。ただし例外として、最後の整数$a_N$を取らなかった場合はパスしたとみなす必要がある。