首页 > 代码库 > UVA 12730 Skyrk's Bar --期望问题

UVA 12730 Skyrk's Bar --期望问题

2024-07-14 07:41:00   219人阅读

题意：有n个地方，现在要站人进去，而每两个人之间至少要隔k个空地，问这n个地方能站的人数的期望是多少。

分析：考虑dp[i]表示 i 个地方能站的期望数，从左往右推，

如果i-k-1<1，那么最多只能站一个，dp[i] = 1，

如果 i-k-1>=1的话，如果第一个人站在第1个位置，那么右边会空出i-k-1个位置，如果站在2位置，那么右边会空出i-k-2个位置......且站在每个位置的概率为1/i，所以： dp[i]=1+(dp[1]+dp[2]+...+dp[i-k-1])/i,  又因为从右边开始站也一样，所以等式右边后面部分要乘以2，

即：dp[i] = 1+(dp[1]+dp[2]+...+dp[i-k-1])*2/i，

因为由左往右递推，所以算dp[i]的时候,dp[i-k-1]以下都是已知的，用sum[i]记录SUM(dp[j]) (1<=j<=i)。

复杂度：O(n)

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define N 1000007double dp[N],sum[N];int main(){    int t,cs = 1,i,n,k;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&k);        memset(dp,0,sizeof(dp));        memset(sum,0,sizeof(sum));        for(i=1;i<=n;i++)        {            if(i-k-1 >= 1)                dp[i] = 1+sum[i-k-1]*2.0/i;            else                dp[i] = 1;            sum[i] = sum[i-1] + dp[i];        }        printf("Case #%d: %.4lf\n",cs++,dp[n]);    }    return 0;}
View Code

 


联系
我们