概率dp水题

Kids and Prizes

Solution:

dp[i]表示到第i个人时获得礼品的期望
dp[i] = dp[i – 1] + 0 * (dp[i – 1] / n) + 1 * ((n – dp[i – 1]) / n)

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
double dp[100001];
int main() { 
    int n = read(), m = read(); dp[1] = 1.0;
    for(int i = 2; i <= m; ++ i)
        dp[i] = dp[i - 1] + 1.0 * (n - dp[i - 1]) / n;
    printf("%.9f", dp[m]);
    return 0;
}

FAVDICE – Favorite Dice

Solution:

dp[i]表示获得i面的期望
dp[i] = dp[i – 1] + 0 * (n / (i – 1)) + 1 * (n / (n – (i – 1))

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
int main() { 
    int t = read();
    double dp[1001] = {0.00, 1.00};
    while(t --) {
        int n = read();
        for(int i = 2; i <= n; ++ i) 
            dp[i] = dp[i - 1] + 1.0 * n / (n - i + 1);
        printf("%.2f\n", dp[n]);
    } return 0;
}

Help Me Escape

Solution:

有点像背包
dp[i][j]表示第j天水平为j的期望 i倒着枚举j就可以降掉
对于妖怪j 如果打得过 就 += tmp * c[j] * c[j]
打不过 += dp[i + c[j]] + 1 //用一天变成dp[i + c[j]]的水准后逃脱
最后 /n即可 多组数据要清空数组

Code:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const double tmp = (1 + sqrt(5)) * 0.5;
int c[1001];
double dp[1000001];
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
int main() { 
    int n; 
    while(scanf("%d", &n) != EOF) { 
        int f = read(), m = -1;
        for(int i = 1; i <= n; ++ i) 
            m = max(m, (c[i] = read()));
        memset(dp, 0, sizeof dp);
        for(int i = m << 1; i >= f; -- i) {
            dp[i] = 0; for(int j = 1; j <= n; ++ j) 
                dp[i] += ((i > c[j]) ? ((int)(tmp * c[j] * c[j])) : (dp[i + c[j]] + 1));
            dp[i] /= n;
        } printf("%.3f\n", dp[f]);
    }
    return 0;
}

Collecting Bugs

Solution:

dp[i][j]表示有i种bug j个子系统里有bug的期望
可以从dp[i + 1], dp[i][j + 1], dp[i + 1][j + 1]转移过来
已有bug概率 i/n 反之 1 – i/n
已有系统概率 j/s 反之 1 – j/s
故可能多出来的概率就是 1.0 – i/n * j/s

Code:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
double dp[1001][1001];
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
int main() { 
    int n = read(), s = read();
    for(int i = n; i >= 0; -- i)
    for(int j = s; j >= 0; -- j) {
        if(i == n && j == s) continue; 
        double inv = 1 - 1.0 * (i * j) / (n * s), now = 0;
        now += dp[i + 1][j] * (1.0 * j / s) * (1 - 1.0 * i / n);
        now += dp[i][j + 1] * (1.0 * i / n) * (1 - 1.0 * j / s);
        now += dp[i + 1][j + 1] * (1 - 1.0 * i / n) * (1 - 1.0 * j / s);
        dp[i][j] = (now + 1) / inv;
    } printf("%.4lf", dp[0][0]);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注