TDPC L - 猫

考え方

ABCでいうと、難しめD問題級。

わりと普通の動的計画法を、少し高速化するだけ。

DPテーブルとして、末尾の猫から左 $1$ 以内にいる猫の最小番号ごとの最大スコアの半分をもつ。
半分にするのは、距離 $1$ 以内にいるペアに両方同じ幸福値が加算されるところ、片方だけ処理するため。

そうしておいて、末尾に猫を $1$ 匹ずつ追加する。

猫 $i$ を追加したとき、そこから左 $1$ 以内にいる猫の最小番号が $j$ であるデータは、以下の和である。

これらは両方とも累積的に処理できるため、猫 $1$ 匹の追加は $O(N)$ でできる。
よって、全体での計算量は $O(N^2)$ となる。

入力を受け取る。

n: 3
f:
{0, 2, 3}
{2, 0, -10}
{3, -10, 0}

以下では、猫を 0-indexed で扱う。
dp[j] は、末尾の猫から左 $1$ 以内にいる猫の最小番号が $j$ の場合の最大スコアの半分とする。

最初は全て $0$ である。

dp: {0, 0, 0}

猫 $0$ を追加しても、まだペアは存在しない。

dp: {0, 0, 0}

猫 $1$ を追加する。
猫 $0$ と猫 $1$ の幸福度は $2$ なので、更新後は次のようになる。

dp: {2, 0, 0}

次に猫 $2$ を追加する。
各 $j$ について、更新前の dp[0] から dp[j] までの最大値と、猫 $2$ から猫 $j$ 以降への幸福度の合計を足す。

$j$	更新前の最大値	猫 $2$ との幸福度の合計	更新後の値
$0$	$2$	$3+(-10)=-7$	$2-7=-5$
$1$	$2$	$-10$	$2-10=-8$
$2$	$2$	$0$	$2$

したがって、最終的な DP テーブルは次のようになる。

dp: {-5, -8, 2}

最大値は $2$ である。
DP テーブルではスコアの半分を持っているので、$2$ 倍した $4$ が答え。

特になし。

特になし。