Typical DP Contest J - ボール
解法
dp[state] = (state で表されるものはすでに倒されている場合の, あと必要な投球数)
とします。
ある state においては, どこか 1 つの座標に向かってボールを投げ続けるのが最適です(外れたからやっぱこっち, とかやるより state が変わるまで同じ場所に投げ続けるのが良い)。
state において x にボールを投げ続けるとすると, 考えられる可能性は,
- 何らかのものにあたって state が変わる
- 何にも当たらなくて state が変わらない
のいずれかです。前者は dfs(nextState) で期待値が計算できますが, 後者は決まりません。そこで, 二分探索をしましょう。dp[state] の値をある値 med に決めうちして後者の期待値を決めて, dp[state] の値を求めます。これが最初に決めうちしたのより大きかったら high を 下げる, などやれば良いです。
const int MAXN = 20; const double INF = 1e9; const int LOOP = 30; int N; int X[MAXN], rX[MAXN]; double dfs(int state); double calc(int x, int state, double med) { double ret = 1; if (x < 0 || x >= MAXN || rX[x] == -1 || (state&(1<<rX[x]))) ret += med; else ret += dfs(state^(1<<rX[x])); return ret; } double dp[1<<16]; double dfs(int state) { double& ret = dp[state]; if (ret >= 0) return ret; if (state == (1<<N)-1) return ret = 0; ret = INF; for (int x = 0; x <= 15; x++) { double low = 0, high = 100; for (int i = 0; i < LOOP; i++) { const double med = (low+high)/2; double tmp = 0; for (int j = -1; j <= 1; j++) tmp += calc(x+j, state, med); tmp /= 3; if (tmp < med) high = med; else low = med; } ret = min(ret, (low+high)/2); } return ret; } int main() { cin >> N; memset(rX, -1, sizeof(rX)); for (int i = 0; i < N; i++) { cin >> X[i]; rX[X[i]] = i; } for (int i = 0; i < 1<<N; i++) { dp[i] = -1; } printf("%.10lf\n", dfs(0)); return 0; }