【POJ2096】Collecting Bugs

题目链接：传送门
题解：
期望DP的第一题（说实话我被吓到了）
转一个kuangbin大神的题解吧

题意：
一个软件有s个子系统，会产生n种bug
某人一天发现一个bug,这个bug属于一个子系统，属于一个分类
每个bug属于某个子系统的概率是1/s,属于某种分类的概率是1/n
问发现n种bug,每个子系统都发现bug的天数的期望。
求解：
dp[i][j]表示已经找到i种bug,j个系统的bug，达到目标状态的天数的期望
dp[n][s]=0;要求的答案是dp[0][0];
dp[i][j]可以转化成以下四种状态:
dp[i][j],发现一个bug属于已经有的i个分类和j个系统。概率为 <nobr> in×js </nobr>;
dp[i][j+1],发现一个bug属于已有的分类，不属于已有的系统.概率为 <nobr> in×(1−js) </nobr>;
dp[i+1][j],发现一个bug属于已有的系统，不属于已有的分类,概率为 <nobr> (1−in)×js </nobr>;
dp[i+1][j+1],发现一个bug不属于已有的系统，不属于已有的分类,概率为 <nobr> (1−in)×(1−js) </nobr>;
整理便得到转移方程

然后看到这里我就不会整理了QAQ（毕竟是第一道）
想半天才明白
假设四种概率分别为 <nobr> p1,p2,p3,p4 </nobr>，那么状态转移就可以写成
<nobr> f[i][j]=p1f[i][j]+p2[i][j+1]+p3[i+1][j]+p4[i+1][j+1]+1 </nobr>
这里面的加一就是这一步走的
我们可以将含 <nobr> f[i][j] </nobr>的都移到左面然后再把系数除过去，就成了
<nobr> f[i][j]=(p2[i][j+1]+p3[i+1][j]+p4[i+1][j+1]+1)/(1−p1) </nobr>
再把 <nobr> p1,p2,p3,p4 </nobr>依次带整理一下就好了（又是整理一下TAT）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1010;
double dp[N][N];
int n,s;

int main()
{
    while(~scanf("%d%d",&n,&s))
    {
        dp[n][s]=0;
        for(int i=n;i>=0;i--)
            for(int j=s;j>=0;j--)
            {
                if(i==n&&j==s) continue;
                dp[i][j]=((n-i)*j*dp[i+1][j]+(n-i)*(s-j)*dp[i+1][j+1]+i*(s-j)*dp[i][j+1]+n*s)/(n*s-i*j);
            }
        printf("%.4f\n",dp[0][0]);  
    }
    return 0;
}