zoj 3329(古典確率dp)

書かないで、人の問題を回して、しかしまだこのようにする道理を理解したいと思っていません.タイトル:
サイコロが3つあり、それぞれk 1、k 2、k 3面があります.
サイコロを投げるたびに、3つの面がそれぞれa,b,cであれば点数を0にし、そうでなければ3つのサイコロの点数の和を加える.
分数がnより大きい場合に終了する.ゲームの期待歩数を求める.初期スコア0
 
分析:
dp[i]は、ゲーム終了までのスコアiを持つ所望のステップ数を示すものとする
則
(1):dp[i]=SUM(p[k]*dp[i+k])+p[0]*dp[0]+1;//p[k]は増加点数kの確率を表し、p[0]は点数が0になる確率を表す
仮定
(2):dp[i]=A[i]*dp[0]+B[i];
則
(3):dp[i+k]=A[i+k]*dp[0]+B[i+k];
(3)を(1)得に代入する:
(4):dp[i]=(SUM(p[k]*A[i+k])+p[0])*dp[0]+SUM(p[k]*B[i+k])+1;
4と2を比較します.
A[i]=(SUM(p[k]*A[i+k])+p[0]);
B[i]=SUM(p[k]*B[i+k])+1;
i+k>nのときA[i+k]=B[i+k]=0であることがわかる
だからdp[0]=B[0]/(1-A[0])は求めることができる

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <list>
#include <cstdlib>
#include <queue>
#include <stack>
#define ALL(a) a.begin(), a.end()
#define clr(a, x) memset(a, x, sizeof a)
#define fst first
#define snd second
#define pb push_back
#define lowbit(x) (x&(-x))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define rep1(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int inf =0x3f3f3f3f;

const int N = 600;
int n,k1,k2,k3,aa,bb,c;
double p[N],a[N],b[N];
void dp(int i){
   if(i > n){ a[i]=b[i]=0; return ;}
   if(a[i] > 0) return ;
   a[i] =p[0]; b[i] = 1;
   for(int k=3;k<=k1+k2+k3;k++){
        dp(i+k);
        a[i]+=p[k]*a[i+k];
        b[i]+=p[k]*b[i+k];
   }
   return ;
}
int main()
{
   int T;
   scanf("%d",&T);
   while(T--){
      scanf("%d %d %d %d %d %d %d",&n,&k1,&k2,&k3,&aa,&bb,&c);
      clr(p,0); p[0]=1.0/(k1*k2*k3);
      rep1(i,1,k1) rep1(j,1,k2) rep1(k,1,k3) if(i!=aa || j!=bb || k!= c)
         p[i+j+k]+=1.0/(k1*k2*k3);

      clr(a,-1); clr(b,-1);
      dp(0);
      printf("%.10lf
",b[0]/(1-a[0]));
   }
   return 0;
}