期望DP入门-蒲公英云

期望DP一般步骤：

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

2.涉及DP状态

原则：

体现线性性质

体现边权

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

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

3.转移

根据边权转移

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

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

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

题意：

思路：

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

可以列方程：

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

求出E=n

思路：

首先概率是一定的

在选的过程中，如果选到了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;
}

题意：

思路：

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

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

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

红色: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;
}

题意：

思路：

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

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;
}

题意：

思路：

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

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

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

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

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;
}

思路：

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

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

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;
}

题意：

思路：

这个的线性性质很明显

设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;
}

思路：

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;
}