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

怼烎@ 2024-04-17 15:17 82阅读 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);
    }