POJ 2096 Collecting Bugs 概率dp（水 - c++编程基础

题目链接：点击打开链接

题意：

点击打开链接

对于这里的dp做法是：

写一个状态x，然后把从x转移出去的方程写出来，即 x = y1+y2+???

其中所有的yi都是已知的。

这样我们就会得到一个方程是从未知到已知。

但是dp是由已知到未知。所以我们再呵呵回来。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
        #include 
        
          using namespace std; const int N = 1005; double dp[N][N]; //dp[i][j] 表示已经找到了i个
         系统, j个bug 的天数 int n, s; double solve(){ dp[n][s] = 0.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)*(s-j)*dp[i+1][j+1] + i*(s-j)*dp[i][j+1] + (n-i)*j*dp[i+1][j] + n*s; dp[i][j] /= n*s - i*j; } } return dp[0][0]; } int main() { while(cin>>n>>s) printf("%.4f\n", solve()); return 0; }