PKU 2151 Check the difficulty of problems

http://poj.org/problem?id=2151
tチームが参加し、m個の問題があるプログラミングコンテストを開く。
この時に、あるチームiが、ある問題jを正解する確率はPijとする。

以下の条件を両方とも満たす確率を求めろというような問題。
・全てのチームが1問以上解く。
・コンテストの優勝チームが最低でもn問以上解く。

多段dp的な問題。
諦めようかと思いましたが、解けたことがすごく嬉しかったので、考えたことを書いてみたいと思います。

まず、あるチームがm問中k問解く確率を求めます。
これはdp[出現した問題数][解いた問題数]という感じで、dpします。
これは
dp[j+1][k]=(問題j+1が解ける確率)*dp[j][k-1]+(問題j+1が解けない確率)*dp[j+1][k]
で求められます。

これで個々のチームがk問正解する確率が求められたので、指定された条件を満たす確率もdpで求めます。
これは
dp[参加したチーム数][n問以上といたチームがあるかないか]という添字で確率を記憶しておけば、

dp[j+1][n問以上解いたチームがある]
=dp[j][n問以上解いたチームがない]*(j+1番目のチームがn問以上正解する確率)+
dp[j][n問以上解いたチームがある]*(j+1番目のチームが1問以上正解する確率)

dp[j+1][n問以上解いたチームがない]
=dp[j][n問以上解いたチームがない]*(j+1番目のチームが1以上n問未満の正解数の確率)

という式が立てられるので、あとはそれを適用するだけです。
２時間以上考えました。動的計画法を多段階的に適用するのが面白く感じました。

double dp[40][40];
double ans[1010][2];

double pp[1000];

main(){
  int m,t,n;
  while(cin>>m>>t>>n,m){
    double p0=1,p1=1;
    memset(ans,0,sizeof(ans));
    ans[0][0]=1;

    rep(i,t){
      memset(dp,0,sizeof(dp));
      dp[0][0]=1;
      rep(j,m){
        cin>>pp[j];
        for(int k=0;k<=j+1;k++){
          dp[j+1][k]=(1-pp[j])*dp[j][k];
          if(k)dp[j+1][k]+=pp[j]*dp[j][k-1];
        }
      }
      double tp1n=0,tpn=0;
      for(int j=1;j<n;j++)tp1n+=dp[m][j];
      for(int j=n;j<=m;j++)tpn+=dp[m][j];
      ans[i+1][0]=ans[i][0]*tp1n;
      ans[i+1][1]=ans[i][1]*(1-dp[m][0])+ans[i][0]*tpn;
    }
    printf("%.3f\n",ans[t][1]);
  }
}