点击打开链接
思路:写出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; }