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

pekempeyのブログ

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

Codeforces Round #346 (Div. 2) G. Fence Divercity

http://codeforces.com/contest/659/problem/G

解法

動的計画法。この解説では h[i]=h[i]-1 とし、1-indexed で扱う。

以下の DP テーブルを使う。

  • dp[i] := i-1 番目と i 番目が少なくとも 1 つ使われているようなパターン数。

遷移パターンは、

  • open: 区間を開く
  • connect: 区間を続ける
  • close: 区間を閉じる
  • open and close: 区間を開いてその場で閉じる

の 4 通り。

  • open: 右に繋げる必要があるので i 番目の選び方は min(h[i],h[i+1]) 通り。
  • connect: 左と右に繋げる必要があるので i 番目の選び方は min(h[i-1],h[i],h[i+1]) 通り。
  • close: 左に繋げる必要があるので i 番目の選び方は min(h[i-1],h[i]) 通り。
  • open and close: i 番目の選び方は h[i] 通り。

f:id:pekempey:20160331151152p:plain

Codeforces Round #346 (Div. 2) G. Fence Divercity

配列を使わない DP はどこか違和感を感じる。