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] 通り。
Codeforces Round #346 (Div. 2) G. Fence Divercity
配列を使わない DP はどこか違和感を感じる。
