概率dp求期待-hdu-4586-Play the Dice

概率dp求期望-hdu-4586-Play the Dice

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4586

题目大意：

有一个色子，n面，每面有个分值a[i],其中有m面比较特殊，当该面出现时，可以再投一次。求最后得分期望。

解题思路：

设所求期望为ans.

考虑投掷一次的情况，如果是m当中的某一面i时，相当于期望增加了a[i],其它所有条件没变，相当于这次没投掷。当投掷到其他面时，得到相应分值。

所以ans=1/n*(a[b[1]]+ans)+1/n*(a[b[2]]+ans)+..1/n*(a[b[m]]+ans)+1/n*a[k]

化简得ans=sum/(n-m)  容易知道m面是等价的。

当sum为0是，为0.sum不为0，而n==m时，ans=INF

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;


//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);


int main()
{
   int n,m;

   while(~scanf("%d",&n))
   {
      int sum=0,a;
      for(int i=1;i<=n;i++)
         scanf("%d",&a),sum+=a;
      scanf("%d",&m);
      for(int i=1;i<=m;i++)
         scanf("%d",&a);
      if(sum==0)
         printf("0.00\n");
      else if(n==m)
         printf("inf\n");
      else
         printf("%.2f\n",sum*1.0/(n-m));
   }
   return 0;
}