期望DP入门

雨点打透心脏的1/2处 2024-03-17 17:05 38阅读 0赞

期望DP一般步骤：

1.模拟过程，找出线性性质，作为阶段（这本质上也是线性DP）

2.涉及DP状态

原则：

体现线性性质

体现边权

根据对期望有无贡献来设计状态

一般在状态设计时需要倒着设计

3.转移

根据边权转移

分为对期望贡献的区别来分开计算贡献

不同情况的**概率贡献**不一样，因此期望贡献也不一样，因此需要分开考虑

考虑权值时可以递归地考虑

![8aedd868b51e4c22ad1ef8f03de6e460.png][]

题意：

![849b1d6c81334122bc8adf49cf25ff7b.png][]

![9067cea865a8430c8502d436a092c7bc.png][]

思路：

设一直选直到1号球被选中的期望选择次数是E

可以列方程：

E=1/n+(1-1/n)\*(E+1)

求出E=n

![85c1b6ee7e1040678c7781820be937aa.png][]

![4732c10d1b0f4547ae470dd4f4e4919d.png][]

思路：

首先概率是一定的

在选的过程中，如果选到了1-K号的某个没被选过的球，剩下就选K-1个，因此线性性质就体现在 剩下还要选多少球 中

所以这个可以记成一个状态

所以最终设出来的状态只有一维：

设dp\[i\]为还剩下i个球选的选择次数的期望

然后考虑转移

选择的决策可以分为，选对选择次数有贡献的，和选对选择次数没有贡献的

选没被选过且编号在1-K的，就是对次数有贡献的，否则就是没有贡献的

前者的期望贡献：dp\[i\]+=k/n\*(dp\[i-1\]+1)，边权为1

后者的期望贡献：dp\[i\]+=(1-k/n)\*(dp\[i-1\]+1)，边权为1

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e3+10;
    const int mod=1e9+7;
    
    int N,Q,K;
    int E[mxn];
    
    int ksm(int a,int b,int mod){
    	int res=1;
    	while(b){
    		if(b&1) res=(res*a)%mod;
    		a=(a*a)%mod;
    		b>>=1;
    	}
    	return res;
    }
    void solve(){
    	cin>>N>>Q;
    	E[1]=N;
    	for(int i=2;i<=N;i++) E[i]=(E[i-1]+N*ksm(i,mod-2,mod)%mod)%mod;
    	while(Q--){
    		cin>>K;
    		cout<<E[K]%mod<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

题意：

![03c073464c584c3897f37cdbdf123a63.png][]

![29a6cfb5c4914f0daa420325109cefce.png][]

思路：

首先看它的决策是什么时，对期望产生贡献

当它选红色且没有被选过的小球时，对期望有贡献，否则就是没有贡献

设计的状态需要体现期望贡献

红色:m

没有被选过:用k表示还需要选多少球，这也体现了线性性质

因为已经选过的红色小球对期望没有贡献，因此可以把选过的红色小球去掉

因此设dp\[k\]\[m\]为还剩下m个红色小球，且还需要选k个不同编号的红色小球的选择次数的期望

转移：

对期望有贡献的部分：m/n\*(dp\[k-1\]\[m-1\]+1)

对期望无贡献的部分：(1-m/n)\*(dp\[k\]\[m\]+1)

然后解个方程就出来了

dp\[k\]\[m\]=dp\[k-1\]\[m-1\]+n/m

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e2+10;
    const int mxe=1e3+10;
    const int mod=1e9+7;
    
    int N,M,Q,K;
    int E[mxn][mxn];
    
    int ksm(int a,int b,int mod){
    	int res=1;
    	while(b){
    		if(b&1) res=(res*a)%mod;
    		a=(a*a)%mod;
    		b>>=1;
    	}
    	return res;
    }
    void solve(){
    	while(cin>>N>>M>>Q){
    		E[1][1]=N;
    		for(int i=1;i<=M;i++){
    			for(int j=1;j<=i;j++){
    				E[i][j]=(E[i-1][j-1]+N*ksm(i,mod-2,mod)%mod)%mod;
    			}
    		}
    		while(Q--){
    			cin>>K;
    			cout<<E[M][K]%mod<<'\n';
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

题意：

![cfeafc4c13d3444280b26235e4867128.png][]

思路：

分为尝试成功和尝试失败两部分进行转移

Code：

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e7+10;
    const int mxe=1e3+10;
    const int mod=1e9+7;
     
    int N;
    int a[mxn],Fac[mxn];
     
    int ksm(int a,int b,int mod){
        int res=1ll;
        while(b){
            if(b&1) res=(res*a)%mod;
            a=(a*a)%mod;
            b>>=1;
        }
        return res%mod;
    }
    void F_init(){
        Fac[0]=1;
        for(int i=1;i<mxn;i++) Fac[i]=(Fac[i-1]*i)%mod;
    }
    void solve(){
        int sum=0;
        for(int i=1;i<=10;i++){
            cin>>a[i];
            sum+=a[i];
        }
        int ans=Fac[sum];
        for(int i=1;i<=10;i++) ans=ans*ksm(Fac[a[i]],mod-2,mod)%mod;
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        F_init();
        while(__--)solve();return 0;
    }

题意：

![b5471e2401484854934335f6767ae799.png][]

思路：

因为计算期望时需要计算概率，计算概率需要n和s这两个参数

因此在设计状态时需要用这两个参数

设dp\[n\]\[s\]为，已经发现了n种bug，s个子系统的天数期望

然后可以分为4种情况来转移，**每种情况的概率贡献不一样**

![13b669af090c42e88488cd6ae4c2762b.png][]

Code：

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e3+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=1e18;
     
    int N,S;
    double dp[mxn][mxn];
     
    void solve(){
        cin>>N>>S;
        dp[N][S]=0;
        for(int i=N;i>=0;i--){
            for(int j=S;j>=0;j--){
                if(i==N&&j==S) continue;
                dp[i][j]=(N*S+(N-i)*j*dp[i+1][j]+i*(S-j)*dp[i][j+1]+(N-i)*(S-j)*dp[i+1][j+1])/(N*S-i*j);
            }
        }
        cout<<fixed<<setprecision(4)<<dp[0][0]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

![59862d90ab31480f8726764bea453378.png][]

思路：

同样的，也是设期望时间，然后列方程（转移）

设逃离迷宫的期望时间为E

![01fc994bf8c1423bae064afc14d72f40.png][]

Code：

#include <bits/stdc++.h>
     
    using namespace std;
     
    const int mxn=1e2+10;
    const int mxe=1e3+10;
     
    int N,idx=0;
    int x[mxn];
     
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++) cin>>x[i];
        int s1=0,s2=0,cnt=0;
        for(int i=1;i<=N;i++){
            if(x[i]<0){
                cnt++;
                s2+=(-x[i]);
            }else{
                s1+=x[i];
            }
        }
        int d1=(s1+s2);
        int d2=(N-cnt);
        int d=__gcd(d1,d2);
        d1/=d,d2/=d;
        if(cnt==N) cout<<"Case "<<++idx<<": inf"<<'\n';
        else cout<<"Case "<<++idx<<": "<<d1<<"/"<<d2<<'\n';
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

题意：

![036cf3dbc8ce4e32a2cd39bf157b6265.png][]

![bdf6dbe028b043618197eae4ba3eed41.png][]

思路：

这个的线性性质很明显

设dp\[i\]为从位置 i 到位置 N 得到金子的价值的期望

它有min(6,N-i)种决策，只要不超过N就行

Code：

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e2+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=1e18;
     
    int tot=0;
    int N;
    int a[mxn];
    double dp[mxn];
    //从位置i到位置N的期望价值
     
    void solve(){
        cin>>N;
        for(int i=0;i<=N;i++) dp[i]=0.0;
        for(int i=1;i<=N;i++) cin>>a[i];
        dp[N]=0.0;
        for(int i=N-1;i>=1;i--){
            for(int k=1;k<=6;k++){
                double p=1.0/min((N-i)*1.0,6.0);
                dp[i]+=(dp[i+k]+1.0*a[i+k])*p;
            }
        }
        cout<<fixed<<setprecision(8)<<"Case "<<++tot<<":"<<" "<<dp[1]+a[1]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

![58960f6d8714467db629938de379f33d.png][]

![5a129810440345aea92b3e433800a40e.png][]

思路：

![174f463f37714f4a86b4f9c6d53b8ceb.png][]

Code：

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
     
    struct ty{
        int to,next;
    }edge[mxe<<2];
     
    int N,tot=0;
    int u,v;
    int head[mxn];
    double ans=0;
     
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    void dfs(int u,int fa,int dep){
        ans+=1.0/(1.0*dep);
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u,dep+1);
        }
    }
    void solve(){
        cin>>N;
        G_init();
        for(int i=1;i<=N-1;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        dfs(1,1,1);
        cout<<fixed<<setprecision(8)<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[8aedd868b51e4c22ad1ef8f03de6e460.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a9fb4ddbbad0448fbcc0c8c6f607f707.png
[849b1d6c81334122bc8adf49cf25ff7b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2ed719c3de6748ca8a972fab77a4f76e.png
[9067cea865a8430c8502d436a092c7bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b57687e9b44649ab9282846727cbe5b2.png
[85c1b6ee7e1040678c7781820be937aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/c3fa30ff24874ff0a08927a9d754a244.png
[4732c10d1b0f4547ae470dd4f4e4919d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/fc67895acb8f456986a7e3fa1b58c685.png
[03c073464c584c3897f37cdbdf123a63.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/24135df89c9146e48ccc4d359dcf8730.png
[29a6cfb5c4914f0daa420325109cefce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/deff035ac0c0474eb9783d39b0e21619.png
[cfeafc4c13d3444280b26235e4867128.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/cd7acabf373e4df9b1cddf17701f53b9.png
[b5471e2401484854934335f6767ae799.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8db8ede66b4642b5bb1e380c277cb329.png
[13b669af090c42e88488cd6ae4c2762b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2f6d750a7b8e42c59801516814af61d6.png
[59862d90ab31480f8726764bea453378.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/00f389c75bc44c3c95bf07f0c24f638c.png
[01fc994bf8c1423bae064afc14d72f40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5d7871ec6045462185c56342f490632f.png
[036cf3dbc8ce4e32a2cd39bf157b6265.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/198321bc9caf4fafb659459fb1ef6cdd.png
[bdf6dbe028b043618197eae4ba3eed41.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e9ba820ad88a41678bac2733135279fc.png
[58960f6d8714467db629938de379f33d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ba8a21749ed443e4929127ac3cf6a5b5.png
[5a129810440345aea92b3e433800a40e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/acc4364a27eb464681c6fdc9125d8c82.png
[174f463f37714f4a86b4f9c6d53b8ceb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b2091bbac32b4a45b3ee7d2777b55aaa.png