Codeforces 498B : Name That Tune

問題リンク : Problem - 498B - Codeforces

問題概要 :
ある人がn曲の歌を決められた順番で歌う
自分はその歌の名前を思い出し次第その人に対して歌の名前を伝える
そうするとその人はその歌をやめて次の歌を歌う
自分は１秒単位でその歌の名前を確率pで思い出す
ただ、t秒その歌を聞いてもその歌の名前を思い出す
このやり取りをn曲全てに対して行う
T秒たった時点で何曲の歌の名前を伝えれるだろうか、その曲数の期待値をもとめよ

解法 :
動的計画法で確率を求める
蟻本第２版のP.67にある重複組み合わせと同様の漸化式の変換を行うことで
O(nT^2) から O(nT) にする
ちなみにその人の実装によるとは思うが、
２つ目の時間のループを1からTまで回したらTLEした
１つの曲に１秒は使うので時間のループは(曲数)からTまでにすると通った
>---ここは自分用---<
式の変形は"性能解析->やはりICPCノート"のP.38をみること
>---以上、自分用でした---<
このタイプのDPはやたら苦手なので類題を探して解きまくりたいが探すのが大変

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int MAX_N = 5010;
int n,T,t[MAX_N];
double p[MAX_N],dp[MAX_N][MAX_N];

int main(){
  cin >> n >> T;
  rep(i,n) {
    cin >> p[i] >> t[i];
    p[i] /= 100.0;
  }

  dp[0][0] = 1;
  rep(i,n) {
    double q1 = pow(( 1 - p[i] ),t[i]-1);
    double q2 = pow(( 1 - p[i] ),t[i]-2);
    if( t[i]-1 < 0 ) q1 = 0;
    if( t[i]-2 < 0 ) q2 = 0;
    REP(j,i+1,T+1) {
      if( t[i] == 1 ) {
	dp[i+1][j] = dp[i][j-1];
	continue;
      }
      if( j-t[i]-1 >= 0 ) dp[i+1][j] += -dp[i][j-t[i]-1] * q1;
      if( j-t[i]   >= 0 ) dp[i+1][j] += -dp[i][j-t[i]] * q2 * p[i];

      dp[i+1][j] += dp[i+1][j-1];
      dp[i+1][j] *= ( 1 - p[i] );

      if( j - t[i] >= 0 ) dp[i+1][j] += dp[i][j-t[i]] * q1;
      dp[i+1][j] += dp[i][j-1] * p[i];
    }
  }

  double answer = 0;
  REP(i,1,n+1) REP(j,i,T+1) answer += dp[i][j];
  printf("%.12f\n",answer);
  return 0;
}