読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #335 (Div. 1) A. Sorting Railway Cars

Codeforces 動的計画法

問題文

codeforces.com

問題概要

配列Aが与えられるので、以下の操作を行ってソートする。

  • 要素をひとつ選んで左端に移動させる
  • 要素をひとつ選んで右端に移動させる

ソートするのに必要な最小の操作回数を求めよ。

解法

ソート完了時には

(左端に飛ばした要素)(移動させなかった要素)(右端に飛ばした要素)

の順に並んでいる。そのため、移動させなかった要素をなるべく多くすれば操作回数を最小化できることが分かる。

移動させなかった要素がソート済みであるためには、要素が連番になっている必要がある。最長の連番部分列を見つけるには、次のようなDPを考えればいい。

dp[i]:=末尾の値がiであるような連番部分列の最長の長さ

自分が提出したコード。DPの更新は簡単にできる。

Codeforces Round #335 (Div. 1) A. Sorting Railway ...

ひとこと

最初LISかと思ったけど全然違った。