解题思路
数学期望裸题 => 复习数学部分的数学期望
求数学期望题型:1.求期望 2.最大游走问题:求每个点的概率分布
利用期望公式转化为DP问题=>dp(状态,硬币数量,剩余没有拿的卡片数量)
学习记忆化搜索的写法!
小技巧
memset(f,-1,sizeof f)
是NAN,可以表示负无穷大
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=17;
int n,m;
double f[2<<16][16*5];
double p[N];
// 记忆化搜索的写法
double dp(int state,int coins,int r)
{
double &v=f[state][coins];
if(v>=0) return v;
if(coins>=r*m) return v=0;
v=0;
for(int i=0;i<n;i++)
if(state>>i&1)
{
v+=p[i]*(dp(state,coins+1,r)+1);
}
else
{
v+=p[i]*(dp(state|1<<i,coins,r-1)+1);
}
return v;
}
int main()
{
cin>>n>>m;
memset(f,-1,sizeof f); //记忆化搜索初始化
for(int i=0;i<n;i++)
cin>>p[i];
printf("%.10lf",dp(0,0,n));
return 0;
}