这道题一定要先读题,题目指出的期望是指在所有可能的状态*这个状态抽卡次数
之和,意思就是对于n个卡牌,有1<<n种状态,需要找到所有符合条件的状态呢
算法1
(状态压缩DP)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = (1<<16)+10,M=85;
double f[N][M],a[N];
//f表示此时的状态也就是卡牌的数量,现在抽了多少次
int one[N];
int get(int x)
{
int res=0;
while(x)
{
x-=x&-x;
res++;
}
return res;
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
for (int i = 0; i < n; i ++ )cin>>a[i];
for(int i=0;i<1<<n;i++) one[i]=get(i);
//找出每个状态下1的个数也就是卡牌的个数
double ans=0;
f[0][0]=1;
for(int i=0;i<1<<n;i++)
for(int j=0;j<=M;j++)
{
if(one[i]+(j-one[i])/m==n)//如果硬币个数足够付款那就记录一下这个状态
{
ans+=f[i][j]*j;//记录这个状态*抽卡次数就是一个期望值
continue;
}
for(int k=0;k<n;k++)
{
if(i>>k&1)f[i][j+1]+=f[i][j]*a[k];//原来有这张卡了,那就是上一次的值*概率加上去
else f[i|(1<<k)][j+1]+=f[i][j]*a[k];//没有这张卡,就是那更新状态
}
}
cout<<ans<<endl;
return 0;
}
算法2
(记忆化搜索)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 85,M=(1<<16)+10;
double f[N][M];
double a[N];
int n,m;
double dfs(int coin,int state,int num,int card)
//分别表示此时硬币数量,此时的状态,此时抽卡次数,此时还剩余的卡牌
{
if(f[coin][state])return f[coin][state];//记忆化搜索模板
//只要搜索过这个状态f>0就不需要再搜索了
if(card*m<=coin)return num;//找到符合题意的直接返回次数即可
double s=0.0;
for(int i=0;i<n;i++)
{
if(state>>i&1)s+=a[i]*dfs(coin+1,state,num+1,card);
else s+=a[i]*dfs(coin,state|(1<<i),num+1,card-1);
}
return f[coin][state]=s;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=0;i<n;i++)cin>>a[i];
cout<<dfs(0,0,0,n);
}
dalao爆搜的代码能在官网上得分吗?
改一下输出精度就能过了,大佬真牛逼