poj 2096 Collecting Bugs 概率DP

思路：仔细读懂题意。

dp[i][j]表示第i个bug，第j个子系统；那么状态转移就有4种可能：

dp[i][j],概率是p1=i/n*j/s;

dp[i+1][j],概率是p2=(n-i)/n*j/s;

dp[i][j+1]，概率是p3=i/n*(s-j)/s;

dp[i+1][j+1]，概率是p4=(n-i)/n*(s-j)/s;

那么就有：

dp[i][j]=p1*(dp[i][j]+1)+p2*(dp[i+1][j]+1)+p3*(dp[i][j+1]+1)+p4*(dp[i+1][j+1]+1)  //注意这里加1是因为本次操作花费一天

=p1*dp[i][j]+p2*dp[i+1][j]+p3*dp[i][j+1]+p4*dp[i+1][j+1]+1

整理的：

dp[i][j]=(n*s+(n-i)*j*dp[i+1][j]+i*(s-j)*dp[i][j+1]+(n-i)*(s-j)*dp[i+1][j+1])/(n*s-i*j)

代码如下：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
#define MAX 1005
using namespace std;
double dp[MAX][MAX];
int main(){
    int n,i,j,s;
    cin>>n>>s;
    dp[n][s]=0.0;
    for(i=n;i>=0;i--)
    for(j=s;j>=0;j--){
        if(i==n&&j==s) continue;
        dp[i][j]=(n*s+i*(s-j)*dp[i][j+1]+(n-i)*j*dp[i+1][j]+(n-i)*(s-j)*dp[i+1][j+1])/(n*s-i*j);
    }
    printf("%.4lf
",dp[0][0]);
    return 0;
}