poj2096 Collecting Bugs（機率期望dp）

題目連結

題目大意：

一個軟體有s個子系統，會産生n種bug

某人一天發現一個bug，這個bug屬于一個子系統，屬于一個分類

每個bug屬于某個子系統的機率是1/s，屬于某種分類的機率是1/n

問發現n種bug，每個子系統都發現bug的天數的期望

分析：

f[i][j] f [ i ] [ j ] 表示出現 i i 種bug，在jj個軟體中發現bug的期望

f[n][s]=0 f [ n ] [ s ] = 0 ，我們求得是 f[0][0] f [ 0 ] [ 0 ]

f[i][j] f [ i ] [ j ] 一共有四種方式的轉移

f[i][j]−>f[i][j]∗in∗js f [ i ] [ j ] − > f [ i ] [ j ] ∗ i n ∗ j s

f[i][j]−>f[i][j+1]∗in∗s−js f [ i ] [ j ] − > f [ i ] [ j + 1 ] ∗ i n ∗ s − j s

f[i][j]−>f[i+1][j]∗n−in∗js f [ i ] [ j ] − > f [ i + 1 ] [ j ] ∗ n − i n ∗ j s

f[i][j]−>f[i+1][j+1]∗n−in∗s−js f [ i ] [ j ] − > f [ i + 1 ] [ j + 1 ] ∗ n − i n ∗ s − j s

期望：機率*花費

f[i][j]=(f[i][j]+1)∗ijns+(f[i][j+1]+1)∗(s−j)ins+(f[i+1][j]+1)∗(n−i)jns+(f[i+1][j+1]+1)∗(n−i)(s−j)ns+1 f [ i ] [ j ] = ( f [ i ] [ j ] + 1 ) ∗ i j n s + ( f [ i ] [ j + 1 ] + 1 ) ∗ ( s − j ) i n s + ( f [ i + 1 ] [ j ] + 1 ) ∗ ( n − i ) j n s + ( f [ i + 1 ] [ j + 1 ] + 1 ) ∗ ( n − i ) ( s − j ) n s + 1

f[i][j]=ijns+(f[i][j+1]+1)∗(s−j)ins+(f[i+1][j]+1)∗(n−i)jns+(f[i+1][j+1]+1)∗(n−i)(s−j)ns1−ijns f [ i ] [ j ] = i j n s + ( f [ i ] [ j + 1 ] + 1 ) ∗ ( s − j ) i n s + ( f [ i + 1 ] [ j ] + 1 ) ∗ ( n − i ) j n s + ( f [ i + 1 ] [ j + 1 ] + 1 ) ∗ ( n − i ) ( s − j ) n s 1 − i j n s

tip

代碼用的是記搜，可能比遞推要慢

注意強制類型轉換和括号的運用：

(double)(i*j)/(double)(n*s)

就不能寫成：

(double)i*j/(double)n*s

（這樣寫隻強制轉換了i和n）

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

using namespace std;

double f[][];
int n,s;
bool vis[][];

double solve(int i,int j)    //n,s
{
    if (vis[i][j]) return f[i][j];

    vis[i][j]=;

    double sum=;
    double p1=(double)((s-j)*i)/(double)(n*s);
    double p2=(double)((n-i)*j)/(double)(n*s);
    double p3=(double)((n-i)*(s-j))/(double)(n*s);
    double p4=(double)(i*j)/(double)(n*s);

    if (j<s) sum=sum+(solve(i,j+)+)*p1;
    if (i<n) sum=sum+(solve(i+,j)+)*p2;
    if (i<n&&j<s) sum=sum+(solve(i+,j+)+)*p3;
    sum=(sum+p4)/(-p4);
    f[i][j]=sum;
    return f[i][j];
}

int main()
{
    scanf("%d%d",&n,&s);
    vis[n][s]=; f[n][s]=;
    printf("%0.4lf",solve(,));
    return ;
}