点击打开链接
思路：写出n=3的情况，就可以看出，会用到n=2的情况，所以毋庸置疑（n=1000），绝壁DP啊！
每往下一层就会乘1/2；因为硬币只有两个面！每一天都只会有两种情况！
又因为最多只会取2n-1次，所以算下当前n天的期望，再加上n---2*n-1的期望和，就是n包面的期望了！ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<iostream> #include<algorithm> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<string> using namespace std; typedef long long ll; double dp[1010][1010]; double ans[1010]; void init() { memset(dp,0,sizeof(dp)); dp[0][0]=1.0; for(int i=0;i<=1000;i++) for(int j=0;j<=1000;j++) { dp[i+1][j]+=dp[i][j]*0.5; dp[i][j+1]+=dp[i][j]*0.5; } for(int i=1;i<=1000;i++) { double sum=dp[i][0]*i; for(int j=i-1;j>=1;j--) { sum+=(i+j)*(dp[i][j]-dp[i][j-1]*0.5); } ans[i]=sum*2.0; } } int main() { init(); int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); printf("%.2lf\n",ans[n]); } return 0; }