zoj 3329 One Person Game 概率dp（有環）

自己看了很多blog才弄明白，自己就不說什麼啦，建議在做幾道簡單題再做這道題，我認為這個blog寫的很好，很具體 http://blog.csdn.net/morgan_xww/article/details/6775853
[cpp] 
#include<iostream> 
#include<cstdio> 
using namespace std; 
#define M 505 
double dp[M],A[M],B[M],p[M]; 
int n,k1,k2,k3,a,b,c; 
int main(){ 
 //   freopen("in.txt","r",stdin); 
    int cases; 
    scanf("%d",&cases); 
    while(cases--){ 
        scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c); 
        double p0=1*(1.0)/k1/k2/k3; 
        for(int i=0;i<500;i++){ 
            p[i]=dp[i]=A[i]=B[i]=0; 
        } 
        for(int i=1;i<=k1;i++){ 
            for(int j=1;j<=k2;j++){ 
                for(int k=1;k<=k3;k++){ 
                    if(i==a&&j==b&&k==c) p[i+j+k]=0; 
                    else p[i+j+k]+=p0; 
                } 
            } 
        } 
        A[0]=p0;B[0]=1; 
        for(int i=n;i>=0;i--){ 
            for(int j=3;j<=(k1+k2+k3);j++){ 
                A[i]+=A[i+j]*p[j]; 
                B[i]+=B[i+j]*p[j]; 
            } 
        } 
        dp[0]=B[0]/(1-A[0]); 
        printf("%.15lf\n",dp[0]); 
    } 
}