poj1741，POJ 3941

2023-11-18 阅读 27 评论 0

摘要：題意：給出n個有m面的骰子，扔一次，求出和，如果和小于等于k，就記1，否則就是和減去k，求最后期望。題解：用滾動數組dp[2][MAX]記錄當前扔到某個數的情況種數，然后......挺水的。。 View Code 1 #include<cstd

題意：給出n個有m面的骰子，扔一次，求出和，如果和小于等于k，就記1，否則就是和減去k，求最后期望。

題解：用滾動數組dp[2][MAX]記錄當前扔到某個數的情況種數，然后......挺水的。。

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 const int N=10005;
 7 int dp[2][N];
 8 int main()
 9 {
10     int n,m,k;
11     while(scanf("%d%d%d",&n,&m,&k),n||m||k)
12     {
13         double all=pow((double)m,double(n));
14         memset(dp,0,sizeof(dp));
15         for(int i=1;i<=m;i++)
16             dp[0][i]=1;
17         int mmax=n*m;
18         double sum=0;
19         for(int i=2;i<=n;i++)
20         {
21             int a=i&1,b=a^1;
22             memset(dp[b],0,sizeof(dp[b]));
23             for(int j=mmax;j>=1;j--)
24                 for(int t=1;t<=m&&t<j;t++)
25                     dp[b][j]+=dp[a][j-t];
26         }
27         int no=(n+1)&1;
28         for(int i=1;i<=k+1;i++)
29             sum+=(double)dp[no][i];
30         for(int i=k+2;i<=mmax;i++)
31             sum+=(double)dp[no][i]*(i-k);
32         printf("%.8lf\n",sum/all);
33     }
34     return 0;
35 }