dp[i][j]表示对应bug1和bug2分别为i,j的状态,到达n,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);
p1,p2,p3,p4对应各种状态的概率。
最后还得把dp[i][j]解出来。
代码:
#include<iostream> #include<vector> #include<string> #include<queue> #include<map> #include<cstdio> #include<cstring> #define maxn 1005 #define INF 0xfffffff #define min(a,b) a<b?a:b #define max(a,b) a>b?a:b using namespace std; double e[maxn][maxn]; int n,s; int main() { int i,j; double p1,p2,p3,p4,p; scanf("%d%d",&n,&s); e[n][s]=0.0; p=1.0*n*s; for(int i=n; i>=0; i--) { for(int j=s; j>=0; j--) { if(i!=n||j!=s) { p1=1.0*(i*j); p2=1.0*(n-i)*j; p3=1.0*i*(s-j); p4=1.0*(n-i)*(s-j); e[i][j]=(p+p2*e[i+1][j]+p3*e[i][j+1]+p4*e[i+1][j+1])/(p-p1); } } } printf("%.4lf\n",e[0][0]); return 0; }