时间限制：1秒

空间限制：262144K

美团点评是综合性生活服务平台，覆盖吃喝玩乐。在休闲娱乐版块，有很多轰趴、桌游、密室逃脱类的项目，适合多人一起玩。下面就是出自团队游戏场景中的一个问题。
有 n 个人排成一排，一开始全部面向前方，然后大家一起转身，随机朝左或是朝右转。
转身后，不断检查队列，如果存在两个面对面的相邻的人，则将这两个人从队列中消除；直到不存在两个面对面的相邻的人。
例如 > 表示向右， < 表示向左
队列“>>><<<”的消除过程为，“>>><<<”到“>><<”到“><”到“”（每次去除一对），最后剩下人数为0。
队列“>><><<<>”的消除过程为，“>><><<<>”到“>><<<>”到“><<>”到“<>”（每次去除一对)，最后剩下人数为2
求最后剩下人数的期望值。
输入描述:
一行一个正整数 n (1 ≤ n ≤ 2000)。


输出描述:
一行一个实数，表示剩下人数的期望值，四舍五入保留三位小数。

输入例子1:
10

输出例子1:
4.618
解法：概率DP。
设f[i][j]表示前i个人中，还有j个向右看的人可以消除，这种状态的期望消除数量， g[i][j]为到达这种状态的概率。
考虑第i + 1的朝向，如果是向右，那么f[i + 1][j + 1] ← f[i][j]/2，
g[i + 1][j + 1] ← g[i][j]/2，如果是向左，那么
f[i + 1][j − 1] ← f[i][j]/2 + g[i][j]，g[i + 1][j − 1] ← g[i][j]/2。(注意 j = 0的情况)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
double f[maxn][maxn], g[maxn][maxn], ans;
//f[i][j]表示前i个人中，还有j个向右看的人可以消除，这种状态的期望消除数量， g[i][j]为到达这种状态的概率。
int n;
int main()
{
    scanf("%d", &n);
    g[0][0] = 1;
    for(int i=0; i<n; i++){
        for(int j=0;j<=i; j++){
            f[i+1][j+1] += f[i][j]/2;
            g[i+1][j+1] += g[i][j]/2;
            if(j){
                f[i+1][j-1] += f[i][j]/2+g[i][j];
                g[i+1][j-1] += g[i][j]/2;
            }
            else{
                f[i+1][j] += f[i][j]/2;
                g[i+1][j] += g[i][j]/2;
            }
        }
    }
    ans = 1.0*n;
    for(int i=0; i<=n; i++) ans -= f[n][i];
    printf("%.3f\n", ans);
    return 0;
}