概率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;}