Typical DP Contest J - ボール

問題

一直線上にn個の目標があり、i番目の座標はxi.
xの位置にボールを投げると、1/3の確率でx-1, x, x+1のどれかに飛ぶ。

最適な戦略を取った時、全ての目標を倒すまでのボールを投げる回数の期待値はいくつか。
前に投げたボールの結果を見て、ボールを投げることができる。

制約条件

0≦xi≦15
n≦16

方針

よくある期待値のメモ化再帰的にやればよい。
rec(bit)を、bitで表される位置に目標が残っているときに、最適な戦略を取った時にボールを投げる回数の期待値とする。

位置iにボールを投げたときの期待値が一番小さくなる位置にボールを投げればよい。
位置iにボールを投げたとき、
起きる結果は
i-1が倒れる
iが倒れる
i+1が倒れる
どこにも当たらない（すでに倒したところに飛ぶ）

のどれか。
期待値は、よくある、どこにも当たらない場合の確率をpとしたら、pで割ると丁度よい感じになるやつ。
Ex = Σpi Ei + (1 - Σpi) Ex + 1の式変形で。

ソースコード

int n;
double dp[1 << 16];
 
double rec(int bit){
	if(bit == 0) return 0;
	double &res = dp[bit];
	if(res >= 0) return res;
	
	res = INF;
	rep(i, 16){
		
		int bit1 = i ? bit & ~(1 << i - 1) : bit;
		int bit2 = bit & ~(1 << i);
		int bit3 = bit & ~(1 << i + 1);
		
		double tmp = 1, p = 0;
		if(bit1 != bit) tmp += rec(bit1) / 3, p += 1.0 / 3;
		if(bit2 != bit) tmp += rec(bit2) / 3, p += 1.0 / 3;
		if(bit3 != bit) tmp += rec(bit3) / 3, p += 1.0 / 3;
		
		res = min(res, tmp / p);
	}
	return res;
}
 
int main(){
	cin >> n;
	int bit = 0;
	rep(i, n){
		int x;
		cin >> x;
		bit |= 1 << x;
	}
	rep(i, 1 << 16) dp[i] = -1;
	printf("%.9f\n", rec(bit));
	
	return 0;
}