概率期望总结（题目合集）-蒲公英云

概率期望总结（题目合集）

怼烎@ 2024-04-17 15:17 139阅读 0赞

1、2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018) E - Explosion Exploit（dfs+概率）

题意：我方n人，血量已知，对方m人，血量已知。现在有d点伤害，一点一点扣，每次伤害对所有活着的人的概率相同。问d次伤害后对面全死的概率。

分析：好题，把概率和dfs结合在了一起，概率题做的少，不擅长。题目数据范围很小，可以直接记忆化搜索，记录每个血量下的人数，用12位十进制数表示双方的状态，需要注意状态转移的方式。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
map<ll,double> mp;
int cnt[2][10];
ll get_sta(){
    ll ans=0;
    for(int i=1;i<=6;i++) ans*=10,ans+=cnt[1][i];
    for(int i=1;i<=6;i++) ans*=10,ans+=cnt[0][i];
    return ans;
}
double dfs(ll sta,int heath){
    if(mp[sta]) return mp[sta];///记忆化
    if(sta<1000000) return 1;
    if(heath==0) return 0;
    int sum=0;///总人数
    for(int i=0;i<2;i++)
        for(int j=1;j<=6;j++)
            sum+=cnt[i][j];
    double ans=0;
    for(int i=0;i<2;i++){
        for(int j=1;j<=6;j++){
            if(!cnt[i][j]) continue;
            cnt[i][j]--;
            cnt[i][j-1]++;
            ll nowsta=get_sta();
            double res=dfs(nowsta,heath-1);
            cnt[i][j]++;
            cnt[i][j-1]--;
            mp[nowsta]=res;
            /// 注意转移方程  当前健康值人数/总人数*上一次转移过来的状态值
            ans+=1.0*cnt[i][j]/sum*res;
        }
    }
    return ans;
}
int main(){
    int n,m,d,h;
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1;i<=n;i++){
        scanf("%d",&h);
        cnt[0][h]++;
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&h);
        cnt[1][h]++;
    }
    double ans=dfs(get_sta(),d);
    printf("%.8f\n",ans);
}