题目链接传送门
题解
期望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×(1js) </nobr>;
dp[i+1][j],发现一个bug属于已有的系统,不属于已有的分类,概率为 <nobr> (1in)×js </nobr>;
dp[i+1][j+1],发现一个bug不属于已有的系统,不属于已有的分类,概率为 <nobr> (1in)×(1js) </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)/(1p1) </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;
}