但是这个题目的问题是精度很难处理，为什么不特判p4就a不了，表示不能理解。
还有一个问题就是如果用维护部分和的办法，每个dp值都通过解方程得到，为什么就会tle，复杂度仍然是n*m的。
因为常数太大还是真的是因为运算过程出现了nan，inf之流的数据，使得运算过慢？
#include#include #include using namespace std; const int maxn=2e3+9; int n,m,k; double p1,p2,p3,p4; double dp[maxn][maxn]; void solve() { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { double sum=0,now=1; for(int j=i;j>=2;j--) { now/=(1-p1); if(j!=i) sum+=(p3*dp[i-1][j]+p4*(j+1<=k))*now; else sum+=(p4*(1<=k))*now; now*=p2; } int from=2; if(from> i) from=1; dp[i][1]=sum/(1-p2*(now/(1-p1)))+now/(1-p1)/(1-p2*(now/(1-p1)))*(p3*dp[i-1][1]+p4*(from<=k)); for(int j=2;j<=i;j++) { dp[i][j]=p2/(1-p1)*dp[i][j-1]+p3/(1-p1)*dp[i-1][j-1]+p4/((1-p1))*(j<=k); } } } int main() { // freopen("in.txt","r",stdin); while(scanf("%d%d%d",&n,&m,&k)!=EOF) { scanf("%lf%lf%lf%lf",&p1,&p2,&p3,&p4); solve(); if(p4<1e-5) printf("0.00000\n"); else printf("%.5f\n",dp[n][m]); } return 0; }