poj2096 Collecting Bugs

 1 #include<cstdio>
 2 #include<iostream> 
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #define LL long long
 6 #define LD long double  
 7 #define  N 100005
 8 using namespace std;
 9 inline int ra()
10 {
11     int x=0,f=1; char ch=getchar();
12     while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
13     while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
14     return x*f;
15 }
16 double dp[1010][1010];
17 int main()
18 {
19     int n,s;
20     double p1,p2,p3,p4;
21     while (scanf("%d%d",&n,&s)!=EOF)
22     {
23     for (int i=0; i<=n; i++) for (int j=0; j<=s; j++) dp[i][j]=0;
24     for (int i=n; i>=0; i--)
25         for (int j=s; j>=0; j--)
26         {
27             if (i==n && j==s) continue;
28             p1=(double)i/n*j/s*1.0;
29             p2=(double)(n-i)/n*j/s*1.0;
30             p3=(double)i/n*(s-j)/s*1.0;
31             p4=(double)(n-i)/n*(s-j)/s*1.0;
32             dp[i][j]=(p2*dp[i+1][j]+p3*dp[i][j+1]+p4*dp[i+1][j+1]+1.0)/(1.0-p1);
33         }
34     printf("%.4f\n",dp[0][0]);
35     }
36     return 0;
37 }