【期望dp】Collecting Bugs

动态规划DP

传送门：POJ2096

题意大致是说一个软件有s个子系统，会产生n种bug。 每天都会发现一个bug，发生在某个子系统中（两者均可能重复）。求找到所有种类的bug，且每个子系统都找到bug的天数的期望。

思路：计算出每种状态的转移状态，算期望即可（代码比较好懂）

代码真心短：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
double p1,p2,p3,p4,pall,f[1030][1030];
int main(){
	while(~scanf("%d%d",&n,&m)){
		for (int i=n;i>=0;i--)
			for (int j=m;j>=0;j--){
				if (i==n && j==m) continue;
				
				p1=(n-i)*(m-j);
				p2=(n-i)*j;
				p3=i*(m-j);
				p4=i*j;
				pall=n*m;
				
				f[i][j]=1.0*(p1*f[i+1][j+1]+p2*f[i+1][j]+p3*f[i][j+1]+n*m)/(pall-p4);
			}
		
		printf("%.4f",f[0][0]);
	}
	
	return 0;
}