绿豆蛙的归宿(概率)

题意

给出一个有向无环的连通图，起点为 1，终点为 N，每条边都有一个长度。

绿豆蛙从起点出发，走向终点。

到达每一个顶点，绿豆蛙等概率选择任意一条道路离开该点。

现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？

思考

概率能用 $D P$ 来做的理论基础：
期望的线性性质: $E(a x+b y)=a E(X)+b E(Y)$

状态表示: $f[i]$ 表示从 $i$ 走到 $n$ 的期望
状态转移方程 $: f[i]=\sum_{i=1}^{k} \frac{1}{k}(w[i]+f(S[i]))$

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>

using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N=1010,mod=1e9+7;

double f[100010];
bool st[100010];

vector<PII> mp[100010];
int n,m;
int a,b,c;
double dfs(int u){
    if(st[u]) return f[u];
    double sz=mp[u].size();
    for(auto nx:mp[u]){
        f[u] += (dfs(nx.first)+1.0*nx.second)/sz;
    }
    st[u]= true;
    return f[u];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        mp[a].push_back({b,c});
    }
    st[n]=true;
    printf("%0.2f",dfs(1));
    return 0;
}

技巧总结

一般起点是唯一的，终点是未知的，定义状态时用“倒推的方法”。

概率能用 $D P$ 来做的理论基础：
期望的线性性质: $E(a x+b y)=a E(X)+b E(Y)$

扑克牌

题意

思路

将问题转为图
起点->终点的路径的期望长度
点(状态) 边(状态转移)
f[a][b][c][d][x][y]:从当前状态跳到终点的期望长度f[a][b][c][d][x][y]:从当前状态跳到终点的期望长度
a张黑桃,b张红桃,c张梅花,d张方块a张黑桃,b张红桃,c张梅花,d张方块
大王状态x,小王状态y:0∼3表示放到abcd4堆中,4表示没有被翻出来大王状态x,小王状态y:0∼3表示放到abcd4堆中,4表示没有被翻出来
则我们只需分析f[a][b][c][d][x][y]能够转移成哪些状态,期望就能用线性公式转移得到

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 14;
const double INF = 1e20;

int A, B, C, D;
double f[N][N][N][N][5][5];

double dp(int a, int b, int c, int d, int x, int y)
{
    double &v = f[a][b][c][d][x][y];
    if (v >= 0) return v;
    int as = a + (x == 0) + (y == 0);
    int bs = b + (x == 1) + (y == 1);
    int cs = c + (x == 2) + (y == 2);
    int ds = d + (x == 3) + (y == 3);
    if (as >= A && bs >= B && cs >= C && ds >= D) return v = 0;

    int sum = a + b + c + d + (x != 4) + (y != 4);
    sum = 54 - sum;
    if (sum <= 0) return v = INF;

    v = 1;
    if (a < 13) v += (13.0 - a) / sum * dp(a + 1, b, c, d, x, y);
    if (b < 13) v += (13.0 - b) / sum * dp(a, b + 1, c, d, x, y);
    if (c < 13) v += (13.0 - c) / sum * dp(a, b, c + 1, d, x, y);
    if (d < 13) v += (13.0 - d) / sum * dp(a, b, c, d + 1, x, y);
    if (x == 4)
    {
        double t = INF;
        for (int i = 0; i < 4; i ++ ) t = min(t, 1.0 / sum * dp(a, b, c, d, i, y));
        v += t;
    }
    if (y == 4)
    {
        double t = INF;
        for (int i = 0; i < 4; i ++ ) t = min(t, 1.0 / sum * dp(a, b, c, d, x, i));
        v += t;
    }

    return v;
}

int main()
{
    cin >> A >> B >> C >> D;
    memset(f, -1, sizeof f);

    double t = dp(0, 0, 0, 0, 4, 4);
    if (t > INF / 2) t = -1;

    printf("%.3lf\n", t);

    return 0;
}

总结

守卫者的挑战

题意

思考

记 $f(i,j,k)$表示考虑前 i 场挑战，成功了 j 次，剩余容量为 k 的概率。当 k>nk>n,之后必然能成功，因此特别记 $f(i,j,n)$ 表示剩余容量不少于 n 的概率，就可以将状态压缩到$n^3$级别。

考虑转移：成功：$ f(i,j+1,k+ai)←pi×f(i−1,j,k)$

失败：$f(i,j,k)←(1−pi)×f(i−1,j,k)$
注意实现时要平移数组，避免负数

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>

using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const LL N=1010,mod=998244353;
double f[210][210][410];//前i次，胜利j次，剩余k
int n,k,l;
double p[210];
int a[220];
int main(){
    cin>>n>>l>>k;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        p[i]/=100;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    k=min(k,n);
    f[0][0][k+n]=1;

    for(int i=1;i<=n;++i)
    {
        int x=a[i];
        for(int j=0;j<i;++j)
            for(int k=0;k<=n+n;++k)
                if(k+x>=0)
                    f[i][j+1][min(n+n,k+x)]+=p[i]*f[i-1][j][k],f[i][j][k]+=(1-p[i])*f[i-1][j][k];
    }
    double ans=0;
    for(int j=l;j<=n;++j)
        for(int k=n;k<=(400);++k)ans+=f[n][j][k];
    printf("%.6lf",ans);
    return 0;
}