概率dp+期望dp 题目列表（一）

时间：2023-03-08 16:26:56
概率dp+期望dp 题目列表（一）

表示对概率和期望还不是很清楚定义。

目前暂时只知道概率正推，期望逆推，然后概率*某个数值=期望。

为什么期望是逆推的，例如你求到某一个点的概率我们可以求得，然后我们只要运用dp从1~n每次都加下去就好了，这样求出来的就是最后的概率。那么期望呢，就是这个概率*数值就行了。但是有时候这么绕来绕去太麻烦了，我们干脆就逆过来。然后我们发现，根据期望的定义，逆过来以后反正做结果并没有太大的改变，dp从n~1就可以了，并且每次都加上数值，然后在for的途中，这个数值是会不断的乘以概率的，所以期望适合用逆推的方法。

题目列表：

①LightOJ 1030 基础题（一）

②Light OJ 1038 基础题 （二）

③Light OJ 1079 背包+概率（三）

④Light OJ 1104 生日悖论（四）

⑤Light OJ 1248 筛子问题（五）

⑥Light OJ 1265 基础题（四）

⑦

⑧

⑨

⑩

一：light OJ 1030 基础题

题目大意：有n个点，每个点有一个val，从1开始出发，到底n个点，每次掷骰子，求到第n个点的期望val是多少？

思路：可以知道对于每个位置，下一个位置只能是后n-i个，所以从这个pos得到的val的期望f(i) = (f(i + 1) + f(i + 2) + … + f(i + 6)) / 6，如果这个位置后不足6，f(i) = (f(i + 1) + … + f(n)) / (n - i)。

期望的代码

//看看会不会爆int! 或者绝对值问题。

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define ALL(a) a.begin(), a.end()

const int maxn =  + ;

int n;

double dp[maxn];

int a[maxn];

int main(){

    int T; cin >> T;

    for (int t = ; t <= T; t++){

        scanf("%d", &n);

        memset(dp, , sizeof(dp));

        for (int i = ; i <= n; i++){

            scanf("%lf", dp + i);

        }

        for (int i = n; i >= ; i--){

            int k = min(, n - i);

            for (int j = ; j <= k; j++){

                dp[i] += (dp[i + j]) * 1.0 / k;

            }

        }

        printf("Case %d: %f\n", t, dp[]);

    }

    return ;

}

当然这道题也可以用概率的代码来写，看这个人的博客吧http://www.cnblogs.com/WABoss/p/5296629.html

学习：懂得基本的期望和概率的知识

二：Light OJ 1038 基础题

思路：预处理即可

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

const int maxn = 1e5 + ;

double dp[maxn];

int main(){

    for (int i = ; i <= maxn - ; i++){

        int cnt = ;

        double sum = ;

        for (int j = ; j * j <= i; j++){

            if (i % j == ){

                sum += dp[j]; cnt++;

                if (j * j != i){

                    sum += dp[i / j]; cnt++;

                }

            }

        }

        sum += cnt;

        dp[i] = sum / (cnt - );

    }

    int t; cin >> t;

    for (int i = ; i <= t; i++){

        int n; scanf("%d", &n);

        printf("Case %d: %.12f\n", i, dp[n]);

    }

    return ;

}

学习：预处理技能

三：Light oj1079

题目大意：抢银行;一个安全概率p,和银行的个数n;接下去给出每个银行可以抢到的钱,还有抢劫这个银行被抓的概率;问在被抓的概率小于等于p的情况下,最多抢到多少钱;

思路:定义dp[i]目前拿了i元还没有被抓住的最大概率

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

const double eps = 1e-;

const int maxn =  + ;

double dp[maxn * maxn];///目前拿了j元还没有被抓住的最大概率

int n;

pair<int, double> p[maxn];

int main(){

    int kase = ;

    int t; cin >> t;

    while(t--){

        memset(dp, , sizeof(dp));

        memset(p, , sizeof(p));

        double pro; int sum = ;

        scanf("%lf %d", &pro, &n);

        for (int i = ; i <= n; i++){

            int val; double t;

            scanf("%d%lf", &val, &t);

            p[i] = mk(val, t);

            sum += val;

        }

        dp[] = ;

        for (int i = ; i <= n; i++){

            for (int j = sum; j >= p[i].first; j--){

                dp[j] = max(dp[j - p[i].first] * ( - p[i].second), dp[j]);

            }

        }

        int ans = ;

        for (int i = ; i <= sum; i++){

            ///printf("%.12f\n", dp[i]);

            if (pro -  + dp[i] > eps){

                ans = i;

            }

        }

        printf("Case %d: %d\n", ++kase, ans);

    }

    return ;

}

四：生日悖论

题目大意：给你n天，至少有几个人来参加，生日为同一天的概率超过50%？

思路：反过来定义dp[i]表示生日都不相同的概率即可。

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

const double eps = 1e-;

const int maxn = 1e5 + ;

double dp[maxn];///生日都不相同的概率

int solve(int n){

    memset(dp, , sizeof(dp));

    dp[] = 1.0;

    for (int i = ; i <= n; i++){

        dp[i] = dp[i - ] * (1.0 * (n - i + ) / n);

        if ( - dp[i] >= 0.5) return i-;

    }

}

int main(){

    int kase = ;

    int t; cin >> t;

    while (t--){

        int n; scanf("%d", &n);

        printf("Case %d: %d\n", ++kase, solve(n));

    }

    return ;

}

五：Light oj 1248

题目大意：给你n个面的东西，投掷，每个面出现至少一次的概率？

也可以看这个人的http://blog.csdn.net/u011686226/article/details/39928597

定义：dp[i]表示还需要扔i个面所需要投掷次数的期望值。然后每一次投掷是有两种可能性，一种是在已经出现过的面中，另一种是在没有出现过的面中，所以我们可以定义dp[i] = i/n * dp[i] + (n-i)/n * dp[i + 1] + 1;所以移项就好了。

如果想要简便一点想的话，就是6*1+6*（1/2）+6*（1/3）+6*（1/4）+6*（1/5）+6*（1/6）。

不过我还是根据期望的定义来写了。。。先算出概率，再求加权和

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

const int maxn = 1e5 + ;

int n;

double dp[maxn];///定义，目前已经出现i种不同颜色的概率

int main(){

    int t; cin >> t;

    int kase = ;

    while (t--){

        scanf("%d", &n);

        for (int i = ; i <= n; i++){

            dp[i] = 1.0 / i;

        }

        double ans = ;

        for (int i = ; i <= n; i++){

            ans += dp[i] * n * 1.0;

        }

        printf("Case %d: %.12f\n", ++kase, ans);

    }

    return ;

}

学习：期望的定义是：每个的概率*权值

六：lightOJ 1265

题目大意：有t个老虎，d个鹿，有以下操作

Ｔ－Ｍ　Ｔ会吃掉Ｍ 
Ｔ－Ｄ　Ｔ会吃掉Ｄ 
Ｄ－Ｄ　Ｎｏｔｈｉｎｇ 
Ｍ－Ｄ　Ｍ可以选择杀与不杀Ｄ 
Ｔ－Ｔ　两只Ｔ会互相残杀（Ｔｗｏ　Ｄｉｅ）

可以看看这个人的http://blog.csdn.net/challengerrumble/article/details/52528951

思路一：定义dp[i][j]表示还有i只老虎，j只鹿的概率，转移就好了

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

const int maxn =  + ;

double dp[maxn][maxn];///还有i只老虎，j只鹿的概率

int n, m;

int main(){

    int T; cin >> T;

    for (int kase = ; kase <= T; kase++){

        scanf("%d%d", &n, &m);

        if (n %  == ) {printf("Case %d: %.10f\n", kase, 0.0); continue;}

        memset(dp, , sizeof(dp));

        dp[n][m] = ;

        for (int i = n; i >= ; i--){

            for (int j = m; j >= ; j--){

                int sum = i * j + i * (i - ) /  + i;///总可能性

                if (sum == ) continue;

                if (j != ) dp[i][j - ] += 1.0 * dp[i][j] * i * j / sum;

                if (i >= ) dp[i - ][j] = 1.0 * dp[i][j] * i * (i - ) /  / sum;

            }

        }

        double ans = ;

        for (int i = ; i <= m; i++) ans += dp[][i];

        printf("Case %d: %.10f\n", kase, ans);

    }

    return ;

}

思路二：定义dp[i] = 目前有i只老虎，老虎全部死亡的概率

因为鹿对我们的存活没有影响，然后我们定义人从来都不杀鹿，这样可以让自己的存活率最大。

所以：

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

const int maxn =  + ;

double dp[maxn];

int n, m;

int main(){

    int T; cin >> T;

    for (int kase = ; kase <= T; kase++){

        scanf("%d%d", &n, &m);

        if (n %  == ){

            printf("Case %d: %.10f\n", kase, 0.0);

            continue;

        }

        dp[n] = 1.0;

        for (int i = n; i >= ; i--){

            int sum = i * (i - ) /  + i;

            if (!sum) continue;

            if (i >= ) dp[i - ] = dp[i] * i * (i - ) /  / sum;

        }

        printf("Case %d: %.10f\n", kase, dp[]);

    }

    return ;

}

学习：需要懂得目前哪些东西是无关变量，再加上一点的贪心即可

七：

八：

九：

相关文章