题解 P2111 【考场奇遇】

· · 题解

感觉dalao们的题解看得似懂非懂 果然我还是太弱了

为了像我一样弱的刚接触概率dp不知道为什么这么转移方程的人

我就写了这篇题解

我们用 f[i][j] 来表示 做i道题中做对j道题的概率

那么可以显而易见地知道 f[i][j] 一定是从 f[i-1][j]或者 f[i-1][j-1]转移过来的

即上一道题要么做对了要么做错了

那么对于这两种情况

① 上一道题的时候已经做对了j道 那么f[i][j] 就是f[i-1][j]* 这道题做错的概率

（i-1道时已经做对了j道那么第i道题中对j道一定因为第i道做错了）

②同理相反的情况下 i-1时做对了j-1道 那么要想i道时做对 j道 那么第i道就一定要做对

对于这个问题 小红和小明答案一样时 小明的正确率就是小红的正确率 错误率就是小红的错误率

而当两人答案不一样时，小明的错误率就变成了小红的正确率，而小红的错误率则是小明的正确率

明白了这一点这个题就非常好写了。

初始状态是

f[0][0]=1;

显然0道中对0道的概率为 1

而且还很明显知道 0道中对0道以上的概率为0 不过本来初始值就是0就不用初始化了

完整代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
#define maxn 100
using namespace std;

void read(int &x){
    x=0;char c=getchar();int flag=1;
    while(c<'0'||c>'9') flag=(c=='-'?-1:1),c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    x=x*flag;
}

int n,q;

int a;

double f[maxn][maxn];

double ans;

int main(){
    read(n);read(a);read(q);
    if(n>50) {
        cout<<"1.000";
        return 0;   
    }
    double p=a/100.0;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        for(int j=0;j<=i;j++){//从做对0道开始 精度问题
            if(c=='0'){
                f[i][j]=f[i-1][j]*p+f[i-1][j-1]*(1-p);
            }
            else{
                f[i][j]=f[i-1][j-1]*p+f[i-1][j]*(1-p);
            }           
        }   
    }
    for(int i=n;i>=q;i--) ans+=f[n][i];
    printf("%.3lf",ans);
}

感谢您看了这么冗长的一段话...