题目意思是有个人喜欢收集bug,然后现在的收集规则是这样的:

一个软件的bug分为n类,软件还有s种子组件,找到一个bug有可能是n种分类中的一种并且还属于s种子组件里面的其中一个组件。

问题是求:找出的bug有n种分类并且还存在于s种子组件里面。


我们可以定义下一次找到bug的情况的四种概率(i为分类的变量,j为子组件的变量):

下一个bug属于已经找到的i种分类,j种子组件 :p1= i*j/n*s;

下一个bug属于已经找到的i种分类,但是不属于已经找到的j种子组件:p2=i*(s-j)/n*s;

下一个bug不属于已经找到的i种分类,但是属于已经找到的j种子组件:p3=(n-i)*j/n*s;

下一个bug属于既不属于已经找到的i种分类,也不属于已经找到的j种子组件:p4=(n-i)*(s-j)/n*s;


定义dp[i][j]为:当前已经找到i个分类,j个子系统,距离找完所有的分类和系统的期望

所以dp[n][s]==0

那么状态转移方程就是:

    dp[i][j]=1.0+p1*dp[i][j]+p2*dp[i][j+1]+p3*dp[i+1][j]+p4*dp[i+1][j+1];

整理可得:

    dp[i][j]=(1.0+p2*dp[i][j+1]+p3*dp[i+1][j]+p4*dp[i+1][j+1])/(1.0-p1);

(加1.0是因为状态转移需要,可以理解为里面的找bug需要一天)


然后代码就容易了。

(第一次做概率dp,看题目想了半天,看题解又看了半天~,感觉废了)


代码:

StatusAccepted
Time360ms
Memory8068kB
Length658
LangC++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=1005;
int n, s;
double dp[maxn][maxn];
double p1, p2, p3, p4, all;
int main()
{
    while(~scanf("%d%d", &n, &s)){
        dp[n][s]=0;
        all=n*s;
        for(int i=n;i>=0;i--){
            for(int j=s;j>=0;j--){
                if(i==n&&j==s)continue;
                p1=(i*j)/all;
                p2=(i*(s-j))/all;
                p3=((n-i)*j)/all;
                p4=((n-i)*(s-j))/all;
                dp[i][j]=(1.0+p2*dp[i][j+1]+p3*dp[i+1][j]+p4*dp[i+1][j+1])/(1.0-p1);
            }
        }
        printf("%.4lf\n", dp[0][0]);
    }
    return 0;
}