算是挺简单的一道概率dp了，如果做了前面的聪聪于可可的话，这题不需要什么预处理，直接概率dp就行了。。。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <math.h> #include <map> #include <queue> #include <sstream> #include <iostream> using namespace std; #define INF 0x3fffffff #define N 2020 double p[N][5]; int n,a,b; double dp[N][5]; void dfs(int s,int k) { if(dp[s][k]>=0) return ; double tmp=0; if(k==1) { double tp=1; for(int i=s+a;i<=s+b;i++) { if(i>n) //超出了界限 { tmp+=tp; break; } dfs(i,2); tmp += tp*p[i][2]*(dp[i][2]+1); //选2的时候的概率 dfs(i,3); tmp += tp*p[i][3]*(dp[i][3]+1); tp*=(1-p[i][2]-p[i][3]); } dp[s][k]=tmp; } else { if(k==2) { double tp=1; for(int i=s+a;i<=s+b;i++) { if(i>n) //超出了界限 { tmp+=tp; break; } dfs(i,1); tmp+=tp*p[i][1]*(dp[i][1]+1); dfs(i,3); tmp+=tp*p[i][3]*(dp[i][3]+1); tp*=(1-p[i][1]-p[i][3]); } dp[s][k]=tmp; } else { double tp=1; for(int i=s+a;i<=s+b;i++) { if(i>n) //超出了界限, { tmp+=tp; break; } dfs(i,1); tmp+= tp*p[i][1]*(dp[i][1]+1); dfs(i,2); tmp+=tp*p[i][2]*(dp[i][2]+1); dfs(i,3); tmp+=tp*p[i][3]*(dp[i][3]+1); tp*=p[i][0]; } dp[s][k]=tmp; } } } int main() { //freopen("//home//chen//Desktop//ACM//in.text","r",stdin); //freopen("//home//chen//Desktop//ACM//out.text","w",stdout); int T; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&a,&b); for(int i=1;i<=n;i++) { for(int j=0;j<=3;j++) scanf("%lf",&p[i][j]); } for(int i=0;i<=n;i++) for(int j=0;j<=3;j++) dp[i][j]=-1; dfs(0,3); printf("%.6lf ",dp[0][3]); } return 0; }